# 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
```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
```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
==有兩種解法，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
```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
```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
==重點 : 可以使用兩個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
1. Method 1: n^2 complexity
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/)
## Decode Ways
拿掉限制後跟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
==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
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
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==
第一步，試著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:
==\*用掉之後仍會剩下\*==
```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
similar to regular matching
差別在於*可為任意char，因此少掉下圖的限制
```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
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
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==
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.
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://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==
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)$
Sign in with Wallet
Connect another wallet