Dynamic Programming Classification
The key to solve DP:
View temporary status as the "sum" of previous status.
Catalan Number
Leetcode 22. Generate Parentheses
From 0 to n, dp[i] represents all valid parenthese results. Next stage dp[i+1] can be viewed as
- Every valid i+1 parenthese can e deformed into a length j parenthese with a () outside it and a length i-j parenthese.
- dp[i+1] will be collection of all combination of (j length parenthese) and (i-j length parenthese).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<vector<string>> dp(n+1);
dp[0] = {""};
for (int i = 0; i <= n; i++){
for (int j = 0; j < i; j++){
for(auto s1 : dp[j]){
for(auto s2 : dp[i-j-1]){
dp[i].push_back("("+s1+")"+s2);
}
}
}
}
return dp[n];
}
};
|
Reverse DP
Leetcode 120. Triangle
From bottom to top, minsum[j] represents the minimum sum from [i][j] to bottom.
- minsum is updated as the minimum of (tmpval + one of neighbors next line).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
if (triangle.size() == 1){
return triangle[0][0];
}
vector<int> minsum(triangle.back());
for (int i = triangle.size()-2; i>=0; i--){
for(int j = 0; j<triangle[i].size(); j++){
minsum[j] = min(minsum[j], minsum[j+1]) + triangle[i][j];
}
}
return minsum[0];
}
};
|
Array Path
Leetcode 53. Maximum Subarray
dp[1][i] denotes the maximum sum of subquery ends at index i, dp[0][i] denotes teh maximum sum of subquery upto index i.
- dp[1][i+1] is either maximum sum of subquery ends at index i-1 or starts at index i.
- dp[1][i+1] is the maximum between maximum sum of subquery upto i-1 or maximum sum of subquery ends at i.
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
int maxSubArray(vector<int>& nums) {
vector<vector<int>> dp(2, vector<int>(size(nums)));
dp[0][0] = dp[1][0] = nums[0];
for(int i = 1; i < size(nums); i++) {
dp[1][i] = max(nums[i], nums[i] + dp[1][i-1]);
dp[0][i] = max(dp[0][i-1], dp[1][i]);
}
return dp[0].back();
}
};
|
Grid Path
Leetcode 62. Unique Paths
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1,0));
for (int i = 0; i<m; i++){
dp[i][0] = 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];
}
};
|
Leetcode 63. Unique Paths II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m+1, vector<int>(n+1,0));
for (int i = 0; i<m; i++){
if(obstacleGrid[i][0] != 0) break;
dp[i][0] = 1;
}
for (int j = 0; j<n; j++){
if(obstacleGrid[0][j] != 0) break;
dp[0][j] = 1;
}
for (int i = 1; i<m; i++){
for (int j = 1; j<n; j++){
if(obstacleGrid[i][j] == 1) continue;
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
|
Leetcode 64. Minimum Path Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int rnum = grid.size();
int cnum = grid[0].size();
vector<int> minsum(cnum+1, 20001);
minsum[1] = 0;
for (int i=0; i<rnum; i++){
for (int j=1; j<=cnum; j++){
minsum[j] = min(minsum[j-1], minsum[j]) + grid[i][j-1];
}
}
return minsum[cnum];
}
};
|
Triangle Path
Leetcode 118. Pascal's Triangle
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> pasctri;
for(int i=0; i<numRows; i++){
pasctri.push_back(vector<int>(i+1, 1));
for (int j=1; j<i; j++){
pasctri[i][j] = pasctri[i-1][j-1] + pasctri[i-1][j];
}
}
return pasctri;
}
};
|
Leetcode 119. Pascal's Triangle II
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> result;
long int res = 1;
result.push_back(res);
for(int i = 0; i < rowIndex; i++){
res = res * (rowIndex - i);
res = res / (i + 1);
result.push_back(res);
}
return result;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> ansArray(rowIndex+1,0);
ansArray[0] = 1;
for (int i = 1; i <= rowIndex; i++)
for (int j = i; j > 0; j--)
ansArray[j] = ansArray[j] + ansArray[j - 1];
return ansArray;
}
};
|