---
# System prepended metadata

title: DP
tags: [Study_aboard]

---

# DP
###### tags: `Study_aboard`
## Climbing stairs

[Introduce to DP by fibonacci](https://medium.com/@ryanyang1221/dynamic-programming-explanation-with-fibonacci-%E7%94%A8%E8%B2%BB%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B8%E5%88%97%E4%BE%86%E8%A7%A3%E9%87%8B%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83-8ce318601d0f)

要爬n階梯子
f(n) = f(n-1) + f(n-2)
f(n-1) 走一步 + f(n-2) 跨2步

= fibonacci

```cpp 
public int climbStairs(int n) {
    // base cases
    if(n <= 0) return 0;
    if(n == 1) return 1;
    if(n == 2) return 2;
    
    int one_step_before = 2;
    int two_steps_before = 1;
    int all_ways = 0;
    
    for(int i=2; i<n; i++){
    	all_ways = one_step_before + two_steps_before;
    	two_steps_before = one_step_before;
        one_step_before = all_ways;
    }
    return all_ways;
}
```

## Unique Paths I 

![](https://i.imgur.com/trj7gXA.png)


```cpp 
class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        //初始化dp，m x 1情况全为1
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }

        //初始化dp，1 x n情况全为1
        for(int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
};
```

## Uniqe Path II 

![](https://i.imgur.com/mY8LCBZ.png)


```cpp 
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int n = obstacleGrid.size();
        if (n == 0) return 0;
        int m = obstacleGrid[0].size();
        
        // f[i][j] = paths(i, j)
        // INT_MIN -> not solved yet, solution unknown
        f_ = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MIN));        
        return paths(m, n, obstacleGrid);
    }
private:
    vector<vector<int>> f_;
    
    int paths(int x, int y, const vector<vector<int>>& o) {
        // Out of bound, return 0.
        if (x <= 0 || y <= 0) return 0;
        
        // Reaching the starting point.
        // Note, there might be an obstacle here as well.
        if (x == 1 && y == 1) return 1 - o[0][0];
        
        // Already solved, return the answer.
        if (f_[y][x] != INT_MIN) return f_[y][x];
        
        // There is an obstacle on current block, no path
        if (o[y - 1][x - 1] == 1) {
            f_[y][x] = 0;
        } else {
            // Recursively find paths.
            f_[y][x] = paths(x - 1, y, o) + paths(x, y - 1, o);
        }
        
        // Return the memorized answer.
        return f_[y][x];
    }
};
```

## Coin change

![](https://i.imgur.com/MHqkg48.png)

==有兩種解法，DP 或是 recursive + memory，兩者總是同時並存的==

similar question : word break ii


solution1:
```cpp 
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        
        vector <int> dp(amount+1,-1);
        dp[0] = 0;
        
        
        for(int i=1;i<=amount;i++){
            
            dp[i] = std::numeric_limits<int>::max();
            
            for(auto coin: coins){
                
                if(i-coin<0)
                    continue;
                
                if(dp[i-coin]==-1)
                    continue;
                
                if(dp[i-coin]+1 < dp[i])
                        dp[i] = dp[i-coin]+1;
            }
            
            if(dp[i]==std::numeric_limits<int>::max()){
                dp[i]=-1;
            }
        }

        return dp[amount];
        
        
    }
};
```
solution2 : 
```cpp 
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> memo(amount + 1, INT_MAX);
        memo[0] = 0;
        return coinChangeDFS(coins, amount, memo);
    }
    int coinChangeDFS(vector<int>& coins, int target, vector<int>& memo) {
        if (target < 0) return - 1;
        if (memo[target] != INT_MAX) return memo[target];
        for (int i = 0; i < coins.size(); ++i) {
            int tmp = coinChangeDFS(coins, target - coins[i], memo);
            if (tmp >= 0) memo[target] = min(memo[target], tmp + 1);
        }
        return memo[target] = (memo[target] == INT_MAX) ? -1 : memo[target];
    }
};
```

## Combination Sum IV 
easy , similar to coin change

![](https://i.imgur.com/Nfp94Jq.png)

```cpp 
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        unsigned long long int dp[target+1];
        int n=nums.size();
        memset(dp,0,sizeof(dp));
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int j=0;j<n;j++){
                
                if(i>=nums[j]){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
};
```

## Minimum Path Sum 
![](https://i.imgur.com/iKPXLwU.png)


```cpp 
class Solution {
public:
   int minPathSum(vector<vector<int>>& grid) {
        
        int rows=grid.size();
        int cols=grid[0].size();
       
        for(int i=1;i<rows;i++)
        {
            grid[i][0]+=grid[i-1][0];
        }
        for(int j=1;j<cols;j++)
        {
            grid[0][j]+=grid[0][j-1];
        }
        
        for(int i=1;i<rows;i++)
        {
            for(int j=1;j<cols;j++)
            {
                grid[i][j]+=min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[rows-1][cols-1];
    }
};
```

## Maximum Subarray 

![](https://i.imgur.com/XKQKfQA.png)

==重點 : 可以使用兩個DP==
curr: 以i為last element 的 maximum subarray 
res : 0:i 的 maximum subarray 


```cpp 
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        
        int curr = nums[0], res = nums[0];
        
        for(int i=1;i<nums.size();i++){
            
            curr = max(curr+nums[i], nums[i]);
            
            res = max(curr, res);
            
        }
        return res;
    }
};
```

## Longest Increasing Subsequence

![](https://i.imgur.com/ZoFscJU.png)

1. Method 1: n^2 complexity

![](https://i.imgur.com/GRLE6un.png)

To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
Formally, the length of the longest increasing subsequence ending at index i, will be 1 greater than the maximum of lengths of all longest increasing subsequences ending at indices before i, where arr[j] < arr[i] (j<i).


```cpp 
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        
        int DP[2500];
        
        for(int i=0;i<2500;i++){
            DP[i] = 1;
        }
        
        for(int i=0;i<nums.size();i++){
            
            for(int j=0;j<i;j++){
                
                if(nums[i]>nums[j]){
                    DP[i] = max(DP[i] , DP[j]+1);
                }
            }
        }
        
        int res = 0;
        
        for(int i=0;i<nums.size();i++){
            res = max(res, DP[i]);
        }
        return res;
    }
};
```
2. Method 2 : Combine with Binary search 
DP + Greedy + Binary Search tree
[solution by geeksforgeeks](https://www.geeksforgeeks.org/longest-monotonically-increasing-subsequence-size-n-log-n/)

![](https://i.imgur.com/2GVAixz.png)

## Decode Ways

![](https://i.imgur.com/qNUIYwx.png)

拿掉限制後跟climbing stairs很像

```cpp 
class Solution {
public:
    int numDecodings(string s) {
        
        vector<int> dp(s.size()+1, 0);
        
        dp[0] = 1;
        dp[1] = (s[0]=='0')?0:1;
        
        
        for(int i=2;i<dp.size();i++){
            
            if(s[i-1]!='0'){
                dp[i]+=dp[i-1];
            }
            
            if(s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')){
                dp[i]+=dp[i-2];
            }
        }
        
        return dp[s.size()];
    }
};
```

## Egg Drop with 2 eggs and N floors
![](https://i.imgur.com/LHIbI5J.png)
![](https://i.imgur.com/RqavVH0.png)

==good problem==

Initial: 
dp 求極值
let dp[i][j]: 在共i層(2~7為五層)中使用j個雞蛋所需確認的moves
1. dp[i][1] = i-1 ex: i=8, 從第0層開始丟到第七層
2. 共j層，丟地i層 = max(dp[i-1][1]+1 // broke , dp[j-i][2]+1  // not broken)
3. 對所有層丟一遍的min為DP值

problem: dp[i][1] = i-1 thus, we don't even need dp[][1] -> reduce 2d dp to 1d

==DP think of base case first, then try to divide subproblems into base case!!==

```cpp 
class Solution {
public:
    int twoEggDrop(int n) {

        vector<int> dp(n+1, INT_MAX);

        dp[0] = 0, dp[1] = 1;
        
        // buttom up
        for(int i=2; i <= n; ++i)
            for(int j=1; j <= i; ++j)
                dp[i] = min(dp[i], max(j-1+1,  1 + dp[i-j]) );

        return dp[n];
    }
};
```
time complexity O(N^2)
space complexity O(N)

## Super egg drop
![](https://i.imgur.com/tcsLhrP.png)
![](https://i.imgur.com/KRSUTHD.png)
please check out egg drop 2 first
solution 1 is just the same as egg drop 2, but slow TLE
Thus, we try to find the optimal point to throw

![](https://i.imgur.com/s1XFgMy.png)

Optimal observation: 
dp[i-1][s-1] 會隨著s變大而遞增
dp[i][j-s] 會隨著s變大而遞減
而最佳解的情況即是在兩著差不多相等，使 worse case 不會太差
所以才有了
```
while (s < j && dp[i - 1][s - 1] < dp[i][j - s]) ++s;
```
且
I------I------I  s1 is the optimal point
I------I----------I s2 is the optimal point
I------I--------------I s3 is the optimal point
可以看到optimal point會遞增，因此可以從上次loop後的值開始繼續
```cpp 
class Solution {
public:
    int superEggDrop(int K, int N) {
		vector<vector<int>> dp(K + 1, vector<int>(N + 1));
        // dp[i][j] i eggs and j floor
		for (int j = 1; j <= N; ++j) dp[1][j] = j;
        for(int i=2;i<=K;i++) dp[i][0] = 0;
        for(int i=2;i<=K;i++) dp[i][1] = 1;
        
		for (int i = 2; i <= K; ++i) {
			int s = 1;// s is the floor to throw
			for (int j = 2; j <= N; ++j) {
                /*
                 * original
                int s = 1;
                dp[i][j] = INT_MAX;
				while (s <= j) {
				    dp[i][j] = min(dp[i][j], max(dp[i - 1][s - 1], dp[i][j - s]) + 1);
                    s++;
                }
                */
                
				while (s < j && dp[i - 1][s - 1] < dp[i][j - s]) ++s;
				dp[i][j] =  max(dp[i - 1][s - 1], dp[i][j - s]) + 1;
			    
            }
		}
		return dp[K][N];
    }
};
```
Time complexity O(KN)



[backtoback very clear solution](https://www.youtube.com/watch?v=iOaRjDT0vjc&t=5s)

## Regular expression matching ==little hard==
![](https://i.imgur.com/xCPDU4j.png)


第一步，試著brute force 破解，令i為s當前要比較的位置，j為p當前要比較的位置，若j+1為*，則將j拆成要重複或不重複兩種情形直到。若要重複，則i+1，若不重複，則j+1。

可以使用recursion來implement

```cpp 
class Solution {
public:
    bool isMatch(string s, string p) {
        
        // special case
        if (p.empty()) return s.empty();
        
        if (p.size() == 1) {
            return (s.size() == 1 && (s[0] == p[0] || p[0] == '.'));
        }
        
        
        if (p[1] != '*') {
            
            if (s.empty()) 
                return false;
            
            return (s[0] == p[0] || p[0] == '.') && isMatch(s.substr(1), p.substr(1));
        }
        
        
        while (!s.empty() && (s[0] == p[0] || p[0] == '.')) {
            //     use *                      * no use
            return isMatch(s.substr(1), p) || isMatch(s,p.substr(2));
        }
        
        // if s[0]!=p[0] -> * = ""
        return isMatch(s, p.substr(2));
    }
};
```
time complexity : O(2^n)

發現recursion會出現很多extra computation -> dynamic programming

dp[i,j] 代表 s[0:i-1] p[0:j-1] 是否match

three situation:

![](https://i.imgur.com/y6IHDpt.png)

==\*用掉之後仍會剩下\*==

```cpp 
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 0; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i][j - 2] || (i && dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'));
                } else {
                    dp[i][j] = i && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
                }
            }
        }
        return dp[m][n];
    }
};
```

time complexity : O(n*m)
## Wildcard matching
![](https://i.imgur.com/FmyWSUG.png)
similar to regular matching
差別在於*可為任意char，因此少掉下圖的限制
![](https://i.imgur.com/EfgFyNG.png)

```cpp 
class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p[i - 1] == '*') dp[0][i] = dp[0][i - 1];
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p[j - 1] == '*') {
                    dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
                } else {
                    dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1];
                }
            }
        }
        return dp[m][n];
    }
};
```
## House Robber
![](https://i.imgur.com/nsYoFUS.png)
![](https://i.imgur.com/SOjdN2v.png)

Initial: Let dp[i] 為偷i的max value
Thus, dp[i] = nums + max(dp[i-2], dp[i-3]) 
Notice that dp[i-4] should be smaller than dp[i-2] because dp[i-2] = max(nums[i-2] + max(dp[i-4], dp[i-5]))

```cpp 
class Solution {
public:
    int rob(vector<int>& nums) {
        
        vector <int> dp(nums.size());
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = max(nums[0]+nums[2], nums[1]);
        
        int res = max(dp[0] ,dp[1]);
        res = max(dp[2], res);
        
        for(int i=3;i<nums.size();i++){
            dp[i] = nums[i] + max(dp[i-2], dp[i-3]);
            res=max(dp[i],res);
        }
        return res;
    }
};
```
Problem : Not simple enough
Sol: Let dp[i] means the max value to stole from 0~i houses

dp[i] = max(nums[i]+dp[i-2], dp[i-1])

## House Robber II 
![](https://i.imgur.com/tHNcU5r.png)
![](https://i.imgur.com/20rCH2m.png)
Initial: 創建兩個dp，dp1紀錄max value from 1 ~ i, dp2紀錄max value from 0 ~ i。則可以得到dp式 dp[i] = max(nums[i]+dp1[i-2], dp2[i-1]) when i=nums.size()-1
```cpp 
class Solution {
public:
    int rob(vector<int>& nums) {
        vector <int> dp1(nums.size()), dp2(nums.size());
        if(nums.size()==1) return nums[0];
        if(nums.size()==2) return max(nums[0],nums[1]);
        
        // 1~i
        dp1[1] = nums[1];
        for(int i=2;i<nums.size()-1;i++){
            dp1[i] = max(nums[i]+dp1[i-2], dp1[i-1]);
        }
        // 0~i 
        dp2[0] = nums[0];
        dp2[1] = max(nums[0],nums[1]);
        
        for(int i=2;i<nums.size()-1;i++){
            dp2[i] = max(nums[i]+dp2[i-2], dp2[i-1]);
        }
        
        return max(nums[nums.size()-1]+dp1[nums.size()-1-2], dp2[nums.size()-1-1]);
    }
};
```


## Brust Balloons ==HARD==

![](https://i.imgur.com/tSMX4Hn.png)

1. 一開始的想法為選擇一個氣球射爆，並計算左邊的max及右方的max，但是發現左方的順序會影響到右方的順序。
2. ==DP 重要做法為反著做==: 假設最後被射破的氣球為K，則左方[i:k-1] and [k+1:j] 皆有固定的邊界。DP[i][j]: [i:j]並且左方為[i-1] and 右方為 [j+1] 的MAX

3. 

![](https://i.imgur.com/FAlQi4n.png)

4. 注意遍歷的順序!!


```cpp 
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        
        int n = nums.size();
        // add 1 to begin and end
        nums.insert(nums.begin(),1);
        nums.push_back(1);
        vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
        
        for(int len=0; len<=n-1 ; len++){
            
            for(int i=1;i<n-len+1;i++){
                
                int j = i+len;
                
                for(int k=i;k<=j;k++){
                    dp[i][j] = max(dp[i][j], nums[i - 1] * nums[k] * nums[j + 1] + dp[i][k - 1] + dp[k + 1][j] );
                }
            }
        }
        return dp[1][n];
    }
};
```

## Edit distance ==Hard==

==Good Problem==

![](https://i.imgur.com/Fl4WtPU.png)

https://www.youtube.com/watch?v=MiqoA-yF-0M

dp[i,j] 代表由字串1的0到i轉變成字串0到j的步驟數

將情況先以最後一個char是否相同作區分

若相同，dp[i, j] = dp[i-1, j-1]
若不同，分為delete， replace， insert 三種可能性
delete : dp[i, j] = dp[i, j-1]
insert : dp[i, j] = dp[i-1,j]
replae: dp[i, j] = dp[i-1,j-1]

```cpp 
class Solution {
public:
    int minDistance(string s, string t) {
        int n=s.length();
        int m=t.length();
        
        int dp[n+1][m+1];
        // filling the table from start is important here
        
        for(int i=1;i<m+1;i++){
            dp[0][i]=i;
        }
        for(int i=0;i<n+1;i++){
            dp[i][0]=i;
        }
        
        for(int i=1;i<n+1;i++){
            for(int j=1;j<m+1;j++){
                
                if(s[i-1]==t[j-1]){
                    // if same they will take the value of diagonal
                    dp[i][j]=dp[i-1][j-1] ;
                }
                
                else{
                    // we will take the miniminum of operations
                        // Insert ,delete,replace
                    dp[i][j]=(1+ min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]}));
                    
                    // insert--> left
                    // delete--> above the block
                    // replace --> diagonally
                }
            }
        }
        
        return dp[n][m];
        
    }
};
```

## Count Number of Special Subsequences ==Hard==
![](https://i.imgur.com/njxvF7T.png)
![](https://i.imgur.com/20oarO6.png)

Initial: 
```dp0```means the number of special sequence of 0.
```dp1```means the number of special sequence of 0,1.
```dp2```means the number of special sequence 0,1,2.

```cpp 
class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        
        vector<long long> dp0(nums.size()),dp1(nums.size()),dp2(nums.size());
        
        int mod = 1e9 + 7;
        
        //dp0 means different ways to choose 0
        dp0[0] = nums[0]==0? 1:0;
        for(int i=1;i<nums.size();i++){
            if(!nums[i]){
                dp0[i] = (2*dp0[i-1] + 1)%mod;
            }   
            else dp0[i] = dp0[i-1];
        }
        
        // dp1 means different ways to choose perfect 0,1
        dp1[0] = 0;
        for(int i=1;i<nums.size();i++){
            if(nums[i]==1){
                dp1[i] = (2*dp1[i-1] + dp0[i-1])%mod;
            }
            else dp1[i] = dp1[i-1];
        }
        
        
        
        // dp2 is the question
        dp2[0] = 0;
        for(int i=1;i<nums.size();i++){
            if(nums[i]==2){
                dp2[i] = (2*dp2[i-1] + dp1[i-1])%mod;
            }
            else dp2[i] = dp2[i-1];
        }
        return dp2[nums.size()-1];
        
    }
};
```
Time complexity:$O(n)$
Space: $O(n)$
Problem: Do not need whole array -> waste space

Sol:
```sum0``` means the number of special sequence of 0.
```sum1``` means the number of special sequence of 0,1.
```sum2``` means the number of special sequence 0,1,2.

```cpp 
class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        long long sum0=0;
        long long sum1=0;
        long long sum2=0;
        int res=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                long long c=0;
                c=sum0+1;  // 0 can come after another 0 or its new occurance
                sum0+=c;
            }
            if(nums[i]==1){
                long long c=0;
                c=sum0+sum1;  //1 can come after any 1 or any 0
                sum1+=c;
            }
            if(nums[i]==2){
                long long c=0;
                c=(sum2+sum1)%1000000007;
                sum2=sum2+c;   //2 can come after any 2 or any 1
                
                res+=c;
                res=res%1000000007;
                
            }
              sum1=sum1%1000000007;
            sum0=sum0%1000000007;
              sum2=sum2%1000000007;
            
            
        }
        return res;
        
    }
};
```
Space $O(1)$