# 資訊科技產業專案設計(HW4)
## **作業(四)**
##### ***Author : 海森堡 Walter(信豪) , 矮鴨 Oopsy(家佑)***
##### 影片連結
>https://youtu.be/X8NcWBA7nVc
>https://youtu.be/Pnkp15UybYQ
## **[1289. Minimum Falling Path Sum II](https://leetcode.com/problems/minimum-falling-path-sum-ii/)**
* **Description**
* 給定一個 n x n 的矩陣，每個位置中都有一個value，在每個row 都必須選一個數字的情況下，算出總和最小的sum，並return sum的值。
* 注意選擇相鄰兩個row的時候，col不可以相同
* 限制條件
* $n = grid.length = grid[i].length$
* $1 \leq n \leq 200$
* $-99 \leq grid[i][j] \leq 99$
---
* Given an n x n matrix where each position contains a value, the task is to compute the minimum sum possible by selecting one number from each row while ensuring that the selected numbers in adjacent rows do not share the same column.
* Constraints:
* $n = grid.length = grid[i].length$
* $1 \leq n \leq 200$
* $-99 \leq grid[i][j] \leq 99$
* Return the value of the minimum sum.
* **Solution**
- [ ] ***Backtracking***
```C++
class Solution {
public:
int res = INT_MAX;
void backtracking(int temp, int r, int c, const vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
if (r == row) {
if (temp < res) {res = temp;}
return;
}
for (int i = 0; i < col; ++i) {
if (i == c) {continue;}
temp += grid[r][i];
backtracking(temp, r + 1, i, grid);
temp -= grid[r][i];
}
}
int minFallingPathSum(vector<vector<int>>& grid) {
int col = grid[0].size();
if (col == 1)
return grid[0][0] ;
for (int j = 0; j < col; ++j) {
backtracking(0, 0, j, grid);
}
return res;
}
};
```
- [ ] ***DP***
```C++
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
vector<vector<int>> dp(row, vector<int>(col, INT_MAX));
dp[row - 1] = grid[row - 1];
for (int r = row - 2; r >= 0; --r) {
for (int c = 0; c < col; ++c) {
for (int x = 0; x < col; ++x) {
if (x != c) {
dp[r][c] = min(grid[r][c] + dp[r + 1][x], dp[r][c]);
}
}
}
}
return *min_element(dp[0].begin(), dp[0].end());
}
};
```
- [ ] ***DP with priority queue support***
```C++
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& grid) {
int rows = grid.size();
int cols = rows;
if (rows == 1) {
return grid[0][0];
}
for (int row = 1; row < rows; ++row) {
vector<int> previousRow = grid[row - 1];
nth_element(previousRow.begin(), previousRow.begin() + 1, previousRow.end());
int min_path_sum = previousRow[0];
int min_path_sum_2nd = previousRow[1];
for (int col = 0; col < cols; ++col) {
if (grid[row - 1][col] == min_path_sum) {
grid[row][col] += min_path_sum_2nd;
} else {
grid[row][col] += min_path_sum;
}
}
}
return *min_element(grid[rows - 1].begin(), grid[rows - 1].end());
}
};
```
* **Complexity Analysis**
* $O(n^n)$
* $O(n^3)$
* $O(n^2)$
* **Mock Interview 草稿**
```
##中文好讀版
🤵🏾 : interviewer
👨🍳 : interviewee
🤵🏾 : 嗨!我是xxx-tech 的資深工程師，很高興跟你進行這場面試，過程中有問題可以隨時發問，
首先請你先介紹你自己吧
👨🍳 : 你好，我也很高興能跟你進行這場面談，我叫海森堡，最近畢業於UCCU-university。
🤵🏾 : 好的，如果準備好那我們就開始問答吧
👨🍳 : 沒問題
(情境)
🤵🏾 : ok , 現在情境是這樣，現在你在一間旅遊公司，負責規劃一個日本自由行，按照天數依序可能是神社、城堡古蹟、泡湯欣賞富士山、購物、參觀動漫或電影景點，而每個行程有一個價位，那第一天或許可以有5個地區的神社可以選擇，同理後面的行程也是有5個地區，因為遊客可能希望盡可能不要連續兩天都在同一個地區，所以必須避免連續日都在同一地區進行行程，但又希望整趟旅程花費盡可能最少。
(原題)
🤵🏾 : 這道題目是這樣的，給定一個 n x n 的矩陣，每個位置中都有一個value，
在每個row 都必須選一個數字的情況下，算出總和最小的sum，並return sum的值。
以下是這題目的一些限制
1. 注意選擇相鄰兩個row的時候，col不可以相同
2. 矩陣中的值 落在-99~99之間
3. 1 <= n <= 200
你有理解題目嗎? 或是你對限制條件有其他疑問都可以發問
👨🍳 : OK, 這裡我理解題目了，這裡有個問題是，每個row都必須選擇一個數字，但對於column有
這樣的限制嗎?
🤵🏾 : 這裡我們並不限制每個column都必須有數字被選擇，你可以專注在row就可
👨🍳 : 好的我這裡有想到一個初步解法，首先定義一個int型別的res，利用一個遞迴函數去逐步把
每個row的數字都選一次。當row == n-1時，判對是否有比當前的res更小，如果有，就更新結果，
然後在往旁邊檢查，把所有可能性都找出來計算一次。
而這樣的複雜度則是在總共n row下，把n個可能的結果都測試一次。所以複雜度是O(n^n)
在n很小的情況下有機會通過測試
🤵🏾 : 好的，但實務上O(n^n)的解法非常有可能無法通過測試，但你可以先將你的想法coding出嗎?
與此同時可能想出一個更有效的算法
👨🍳 : coding...
請問是否允許利用額外的空間來進行記憶? 或者是可以修改原本陣列中的數字來進行計算?
🤵🏾 : 可以，你可以先考慮使用額外空間來計算
👨🍳 : 這裡我會利用dp的概念，找出row = 1...n 每一層的每位置最佳解，然後每次只需要檢查上
層最佳解即可，這裡可以將複雜度壓到 O(n^3)
🤵🏾 : good! 你成功的把複雜度壓縮到可以在合理時間完成的程度，但是這題的最佳解事實上還有優化的空間
請問你能不能找出你的code中可以進行優化的部分呢?
👨🍳 : 恩...好的我大概知道可以怎優化，因為我在進行找尋最佳解的時候忽略題目的暗示，
事實上最佳解如果是在上層的同一col，這時候我們只需要找到次佳解就可，
根本不需要找出全部的可能性，所以我們只需要利用priority queue去找出前兩項最小值。
利用if...else 判斷要使用哪一個當成最佳解。這樣子時間複雜度可以壓到 O(n^2)，
空間複雜度如果不改變原本陣列，最差的狀況需要O(n^2 + 2) 跟O(n^3) 解法比起來
僅需要兩個額外空間，但時間複雜度可以下降一個多項式次方
🤵🏾 : 沒錯!那麼請你將最佳解coding出來
👨🍳 : coding....
```
```
##[ENG] - not done yet
🤵🏾 : Hi! I'm a senior engineer at xxx-tech. I'm glad to have this interview with you.
Feel free to ask any questions during the process. First, please introduce yourself.
👨🍳 : Hello, I'm also pleased to be having this discussion with you.
My name is Heisenberg, and I recently graduated from UCCU-university.
🤵🏾 : Great! If you're ready, let's begin the interview.
👨🍳 : No problem.
(scenario version)
🤵🏾 : The scenario involves planning an independent trip to Japan with different destinations for each day.
The schedule might include visits to shrines, historical castles, hot springs with views of Mount Fuji, shopping districts, and visits to anime or movie-related spots.
Each schedule option has a cost associated with it.
For instance, on the first day, there might be five shrine options to choose from.
Similarly, each subsequent day offers choices from five different regions.
To provide variety, visitors prefer not to visit the same region on consecutive days.
Thus, the goal is to plan the itinerary to minimize the overall cost while ensuring there are no consecutive days in the same region.
(original question)
🤵🏾 : So, here is the question. Given an n x n matrix where each position contains a value, you need to find the minimum sum by choosing one number from each row, ensuring that adjacent rows don't share the same column. Here are some constraints:
1. Pay attention that when choosing two adjacent rows, the columns cannot be the same.
2. The values in the matrix are within the range of -99 to 99.
3. 1 <= n <= 200.
Do you understand the question, or do you have any other queries about the constraints?
👨🍳 : OK, I understand the question. One clarification: Each row must select one number, but is there a similar restriction on the columns?
🤵🏾 : We don't impose a restriction that each column must have a selected number. You can focus on the rows.
👨🍳 : Okay, I have come up with a simple solution. First, define an integer variable 'res'. Use a recursive function to iteratively select numbers from each row. When row == n-1, check if it's smaller than the current 'res'. If so, update the result. Then, check the adjacent possibilities by computing all combinations. The complexity here is trying n possibilities for each of n rows, resulting in a complexity of O(n^n). This might work for small n values.
🤵🏾 : Okay, but practically, a solution with O(n^n) complexity is unlikely to pass tests. Could you code your approach? Meanwhile, try to come up with a more efficient algorithm.
👨🍳 : (Starts coding) Is it allowed to use extra space for computation? Or can I modify the original array while calculating?
🤵🏾 : Yes, you can consider using additional space for computation.
👨🍳 : I'll employ the concept of DP to find the optimal solution for each position from row = 1 to n. Then, by checking the optimal solution from the previous layer, I can reduce the complexity to O(n^3).
🤵🏾 : Good! You've successfully reduce the complexity to a solvable level. However, there's still room for optimization in the optimal solution for this question. Can you identify parts of your code that could be optimized?
👨🍳 : Hmm...okay, I have an idea for optimization. I ignored the hint from the question while searching for the optimal solution. In reality, if the best solution is in the same column of the upper layer, we only need to find the next best solution. We don't need to explore all possibilities. So, we can use a priority queue to find the two smallest values. Then, based on an if...else condition, choose which one should be used as the best solution. This can reduce the time complexity to O(n^2). The space complexity, without altering the original array, would require at most O(n^2 + 2) compared to O(n^3) solutions. It only needs two additional spaces but reduces the time complexity by a polynomial factor.
🤵🏾 : That's correct! Please go ahead and code the optimized solution.
👨🍳 : (Starts coding)
🤵🏾 :Great! It's impressive how quickly you come up with this solution. Since we're out of time, this is the end of today's interview, thank you for your participation.
👨🍳 :Thank you!
```
## **[198. House Robber](https://leetcode.com/problems/house-robber/description/)＆[213. House Robber II](https://leetcode.com/problems/house-robber-ii/)**
* **Description(House Robber)**
* You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
* Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
* Constraints:
* 1 <= nums.length <= 100
* 0 <= nums[i] <= 400
* **Solution**
- [ ] ***DP***
```C++
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==1) return nums[0];
vector<int> dp(n+1,0);
dp[1] = nums[0];
for(int i=2;i<n+1;++i) {
dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
}
return dp[n];
}
};
```
- [ ] ***DP(space complexity=O(1))***
```C++
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==1) return nums[0];
int a = 0;
int b = nums[0];
for(int i=1;i<n;++i) {
int c = max(b, a+nums[i]);
a = b;
b = c;
}
return b;
}
};
```
* **Complexity Analysis**
* time: O(n)
* space: O(n) -> O(1)
* **Description(House Robber II)**
* You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
* Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
* Constraints:
* 1 <= nums.length <= 100
* 0 <= nums[i] <= 1000
* **Solution**
- [ ] ***DP***
```C++
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==1) return nums[0];
int a = 0;
int b = nums[0];
for(int i=1;i<n-1;++i) {
int c = max(b, a+nums[i]);
a = b;
b = c;
}
int max1 = b;
a = 0;
b = nums[1];
for(int i=2;i<n;++i) {
int c = max(b, a+nums[i]);
a = b;
b = c;
}
return max(max1, b);
}
};
```
* **Complexity Analysis**
* time: O(n)
* space: O(1)
* **Mock Interview 草稿**
```
🤵🏾 : interviewer
👨🍳 : interviewee
🤵🏾 :Hello, can you hear me?
👨🍳 :Yes, I can hear you.
🤵🏾 :Great! So I'm Walter, a senior engineer at funfun-tech. I'm your interviewer today.
👨🍳 :Hello Walter, I'm Oopsy.
🤵🏾 :Okay.Let’s get started. A factory has a linear production line that generates a row of components in each cycle.
🤵🏾 :Each component has varying degrees of defects, with higher value associated with lesser defects.
🤵🏾 :However, when components are retrieved from the production line, they undergo a temperature change, causing damage to the components on their immediate left and right, which means adjacent components cannot be taken.
🤵🏾 :Please devise a method to maximize the total value of components that can be retrieved from the production line.
👨🍳 :I can understand that I will receive a linear set of data, and their values are integers. I cannot choose two consecutive integers, and I hope to get the maximum sum of these integers. Is that correct?
🤵🏾 :Yes.
👨🍳 :Okay, I'd like to give an example to double-check if my understanding is correct.
🤵🏾 :Sure.
👨🍳 :If I get an input like [1,2,3,1], than I can choose the first one and the third one, but I cannot choose the second one and the third one, cause they're adjancy, right?
🤵🏾 :Yes. So what is the output for this example?
👨🍳 :I will choose the first one and the third one, which are 1 and 3, and the output should be 1+3=4.
🤵🏾 :That's right. How would you solve this problem?
👨🍳 :My approach is using dynamic programming. If I choose the component number i-1, than I can't choose the component number i.So I can generate a simple formula like this one: dp[i] = max(dp[i-1],dp[i-2]+nums[i])
🤵🏾 :Sounds good, let's start coding.
(coding & testing)
🤵🏾 :Your approach is good. But in this code, your space complexity is O(n). Can you figure out a way to cost down your space?
👨🍳 :I see. Since the process of the dynamic programming only involves the previous two elements, there's no need to keep track of all values. We can use just three variables instead.
🤵🏾 :Good! Please go ahead and code the optimized solution.
(coding & testing)
🤵🏾 :Great! There is a further question I would like to ask.
🤵🏾 :If the factory's production line becomes circular instead of linear, with all other conditions unchanged, how would you solve this problem?
👨🍳 :Okay, so the only different part is the production line become circular, which means that I cannot choose the first component and the last component at the same time, is that correct?
🤵🏾 :Correct. You can start talking about your approach.
👨🍳 :Since I cannot choose the first component and the last component at the same time, I can seperate this problem into two condition.
👨🍳 :In the first condition, I will run the linear version approach from the first component to the (n-1)th component.
👨🍳 :In the second condition, I will run the linear version approach from the second component to the nth component.
👨🍳 :Finally I will get two total value from those two condition, and I just have to choose the bigger one to be the final output.
🤵🏾 :Great! It's impressive how quickly you come up with this solution. Since we're out of time, this is the end of today's interview, thank you for your participation.
👨🍳 :Thank you!
```
Sign in with Wallet
Connect another wallet