# **演算法作業 HW12**
<font size=6>**Dynamic Programming**</font>
---
<font size=5>**1. 小偷行竊(2)**</font>
---
[64. House Robber II](https://leetcode.com/problems/house-robber-ii/)
環形的話頭尾互相影響，分兩種情況討論。
算出拿第一棟和不拿的答案後取最大的就行。
完全靠自己，完成時間：30分鐘。

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()<4)//只能選一棟情況
            return *max_element(nums.begin(), nums.end());
        int n=nums.size();
        vector<int>dp1(n,0),dp2(n,0);
        //分兩種情況討論
        //雖然是環形，但在算式的推導上是一樣的
        //拿第一棟
        dp1[0]=nums[0];
        dp1[1]=nums[0];
        for(int i=2;i<n-1;++i)
            dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i]);
        //不拿第一棟
        dp2[0]=0;
        dp2[1]=nums[1];
        for(int i=2;i<n;++i)
            dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i]);
        return max(dp1[n-2],dp2[n-1]);
    }
};


<font size=5>**2. 最佳買賣股票的時機(當有交易費時)**</font>
---
[714. Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/)
分成兩種狀態去紀錄。
如果是買進就接上一次最大的賣出利益。
賣出就接上一次最大的買入利益。
最後回傳最大利益的買入(操作一定由買入開始)。
參考網上答案，完成時間：20分鐘。

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n=prices.size();
        int pick,notpick;
        vector<vector<int>>dp(n+1,vector<int>(2,0));
        //從後往前(從後面操作才能確定當下是最大利益)
        for(int i=n-1;i>=0;--i)
        {
            for(int j=0;j<=1;++j)
            {
                //0代表賣出，1代表買進
                if(j == 1)//買進
                {
                    //不選擇以此價格做操作，接續上一次買進操作的最大利益
                    notpick = dp[i+1][1];
                    //以此價格買進加上後面賣出操作後的最大利益
                    pick = -prices[i] + dp[i+1][0];
                }
                else//賣出
                {
                    //不選擇以此價格做操作，接續上一次賣出操作的最大利益
                    notpick = dp[i+1][0];
                    //以此價格賣出加上後面買進操作後的最大利益
                    //賣出時完成一次操作扣除手續費
                    pick = prices[i] - fee + dp[i+1][1];
                }
                dp[i][j] = max(pick,notpick);
            }
        }
        return dp[0][1];//一定是由買進開始，所以回傳買進最大利益
    }
};


<font size=5>**3. 分為總和相等的二堆**</font>
---
[416. Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)
這一題很久之前就做過，也是我的期末選題。
題目不要求組合，所以僅僅只是記錄各種和而已。
用dp來寫不難，重點是可以把操作省略。
利用位移運算的特性一次對多個狀態做更新。
很特別，因此我對這題的印象特別深。
完全靠自己，完成時間：1分鐘。

class Solution {
public:    
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto n:nums)//計算總和
            sum+=n;
        if(sum&1)//總和是奇數
            return false;
        //只要計算一個子集有沒有到總和一半就好
        sum/=2;
        bitset<10001>bit(1);//max possible sum/2 = 10000
        for(int i:nums)
            bit|=(bit<<i);
        //每個bit代表在那一位的數字，往左推就相當於加上去，
        //並且用or運算不會讓先前的紀錄消失
        //於是最後每種組合能得到的數都會記錄在裡面
        return bit[sum]&1;
    }
};


<font size=5>**4. 存積雨水**</font>
---
[42. Trapping Rain Water](https:///leetcode.com/problems/trapping-rain-water/)
這題之前也做過了，要記錄的是該點左右邊的最高點。
兩邊更低一邊減掉該點高度就是該點水量。
完全靠自己，完成時間：1分鐘。

class Solution {
public:
    int trap(vector<int>& height) {
        int N = height.size(), ans = 0;
        
        vector<int> left(N, 0), right(N, 0);
        //最左右不會積水，可以忽略
        for(int i = 1; i < N; ++i)//找出該點左邊最高 
            left[i] = max(left[i - 1], height[i - 1]);
        
        for(int i = N - 2; i >= 0; --i)//找出該點右邊最高
            right[i] = max(right[i + 1], height[i + 1]);
        
        for(int i = 1; i < N - 1; ++i)//右邊和左邊最低減上該點高度就是積水高度
            ans += max(0, min(left[i], right[i]) - height[i]);
        
        return ans; 
    }
};


<font size=5>**5. 矩陣中最長的遞增路徑**</font>
---
[329. Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/)
用dfs往下探訪和紀錄，探訪過的點就直接挪用紀錄。
完全靠自己，完成時間：3分鐘。

class Solution {
public:
    int dfs(vector<vector<int>>&dp,vector<vector<int>>&mat,
        int m,int n,int i,int j,int pre)
    {
        if(i>=m || j>=n || i<0 || j<0 || mat[i][j] <= pre)
            return 0;
        if(dp[i][j])//之前有紀錄就直接回傳
            return dp[i][j];
        int l = dfs(dp,mat,m,n,i-1,j,mat[i][j]);//左
        int r = dfs(dp,mat,m,n,i+1,j,mat[i][j]);//右
        int u = dfs(dp,mat,m,n,i,j-1,mat[i][j]);//上
        int d = dfs(dp,mat,m,n,i,j+1,mat[i][j]);//下
        dp[i][j] = max({l,r,u,d})+1;
        return dp[i][j];
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        //用dfs下去尋訪，紀錄每個點探訪後升序最長長度
        //如果該點被探訪過就直接取用之前的紀錄
        //過程中紀錄最大值
        int m=matrix.size(),n=matrix[0].size();
        vector<vector<int>>dp(m,vector<int>(n,0));
        int maxl=0;
        for(int i=0;i<m;++i)
        {
            for(int j=0;j<n;++j)
                maxl=max(maxl,dfs(dp,matrix,m,n,i,j,-1));//更新最大值
        }
        return maxl;
    }
};


<font size=5>**6. 本周心得**</font>
---
大部分的題目都做過了，不過在看一次果然還是覺得dp好難。

---
若有錯誤歡迎指正