最大最小值DP
Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i] 有时候也会min(f[x-1]+1, f[x])， 特别时重复走过x
746. Min Cost Climbing Stairs
到i的路径来自于i-1和i-2。最后一步可以为n-1或者n的总cost。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int ss = cost.size();
vector <int> memo (ss+1, 0x6fffffff);
memo[0] = 0; memo[1] = cost[0];
for (int i=2; i<=ss; i++) {
memo[i] = min(memo[i-1], memo[i-2]) + cost[i-1];
}
return min(memo[ss-1], memo[ss]);
}
};
64. Minimum Path Sum
Note: You can only move either down or right at any point in time.
f[n][m] = min(f[n-1][m], f[n][m-1]) + f[n][m];
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> memo(n+1, vector<int>(m+1));
// 給memo[0][1], memo[1][0]赋初值0
for (int i=2; i<=n; i++) {
memo[i][0] = 0x6fffffff;
}
for (int i=2; i<=m; i++) {
memo[0][i] = 0x6fffffff;
}
for (int i=1; i<=n; i++) {
for (int j=0; j<=m; j++) {
memo[i][j] = min(memo[i-1][j], memo[i][j-1]) + grid[i-1][j-1];
}
}
return memo[n][m];
}
};
改良版->不需要memo, 用if处理padding，
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size();
// f[n][m] = min(f[n-1][m], f[n][m-1]) + f[n][m];
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if (j>0 && i>0)
grid[i][j] += min(grid[i-1][j], grid[i][j-1]);
else if (i>0)
grid[i][j] += grid[i-1][j];
else if (j>0)
grid[i][j] += grid[i][j-1];
}
}
return grid[n-1][m-1];
}
};
322. Coin Change
f[n] = min(f[n-coins[i]], f[n-coins[i+1]], ....) + 1; memo[0] = 0; 如果memo[amount]是0x6fffffff，则表示没走到这过（没发生过更新）返回-1。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
int ss = coins.size();
vector<int> memo(amount+1, 0x6fffffff);
memo[0] = 0;
for (int i=1; i<=amount; i++) {
for (int j=0; j<ss; j++) {
if (coins[j]>i) continue;
memo[i] = min(memo[i-coins[j]] + 1, memo[i]);
}
}
return memo[amount] != 0x6fffffff? memo[amount] : -1;
}
};
931. Minimum Falling Path Sum
类似 Minimum Path Sum，
f[x][y] = min(f[x-1][y], f[x-1][y-1], f[x-1][y+1]) + f[x][y]， 可直接在矩阵上操作， 然后判断边缘条件决定转移方程（e.g. y==0时候,忽略f[x-1][y-1]）。
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& A) {
int n = A.size(), m = A[0].size();
for (int x=1; x<n; x++) {
for (int y=0; y<m; y++) {
if (y && m-1-y)
A[x][y] += min(A[x-1][y-1], min(A[x-1][y], A[x-1][y+1]));
else if (y)
A[x][y] += min(A[x-1][y], A[x-1][y-1]);
else if (m-1-y)
A[x][y] += min(A[x-1][y], A[x-1][y+1]);
else
A[x][y] += A[x-1][y];
}
}
return *min_element(A[n-1].begin(), A[n-1].end());
}
};
!983. Minimum Cost For Tickets Medium
f[day]相当于当日若出行，最低总票价
f[day] = min(f[day-1]+ticket_1, f[day-7]+ticket_2, f[day-30]+ticket_2); if f[day] not in days -> f[day] = f[day-1];
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int max_day = days[days.size()-1];
vector <int> memo(max_day+1);
int idx = 0; // memo[0] = *min_element(costs.begin(), costs.end());
for (int i=1; i<=max_day; i++) {
if (i<days[idx]) memo[i] = memo[i-1];
else {
if (i>29)
memo[i] = min(min(memo[i-1]+costs[0],
memo[i-7]+costs[1]),
memo[i-30]+costs[2]);
else if (i>6)
memo[i] = min(min(memo[i-1]+costs[0],
memo[i-7]+costs[1]),
costs[2]);
else
memo[i] = min(min(memo[i-1]+costs[0],
costs[1]),
costs[2]);
idx ++;
}
}
return memo[max_day];
}
};
!650. 2 Keys Keyboard Medium
更新都是来自公约数，所以对2n和1n/2循环
dp[n] = min(dp[n], dp[n/cnt] + n/cnt + 1 - 1); AA 复制到 AAAA只要一次粘贴操作
class Solution {
public:
int minSteps(int n) {
if (n == 1) return 0;
vector<int> dp(n+1, 0x6fffffff);
dp[1] = 0, dp[2] = 2;
for (int i=3; i<=n; i++) {
for (int j=i/2; j>0; j--) {
if (i%j) continue;
// AA -> AA AA just need to copy once!
dp[i] = min(dp[i], dp[j] + i/j + 1 - 1);
}
}
return dp[n];
}
};
再简化版 -> f[2]也符合规律
class Solution {
public:
int minSteps(int n) {
vector<int> dp(n+1, 0x6fffffff);
dp[1] = 0;
for (int i=2; i<=n; i++) {
for (int j=i/2; j>0; j--) {
if (i%j) continue;
// AA -> AA AA just need to paste once! and copy also needs one operation. so 1-1;
dp[i] = min(dp[i], dp[j] + i/j + 1 - 1);
}
}
return dp[n];
}
};
279. Perfect Squares Medium
f[n] = min(f[n-sqr_num[i]] + 1, f[n]);
int numSquares(int n) {
if (!n) return 0;
vector<int> dp(n+1, 0x6fffffff), sqr_nums;
for (int i=1; i<=static_cast<int>(sqrt(n)); i++) {
sqr_nums.push_back(pow(i, 2));
}
int ss = sqr_nums.size();
dp[0]=0;
for (int i = 1; i<=n; i++) {
for (int j = 0; j < ss; j++) {
if (sqr_nums[j]>i) break;
dp[i] = min(dp[i-sqr_nums[j]] + 1, dp[i]);
}
}
return dp[n];
}
};
简单优化
找小于等于n的次方for (int i=1; ii<=n; i++) sqr_nums.push_back(ii);
class Solution {
public:
int numSquares(int n) {
// f[n] = min(f[n-sqr_num[i]] + 1, f[n]);
vector<int> dp(n+1, 0x6fffffff), sqr_nums;
for (int i=1; i*i<=n; i++) sqr_nums.push_back(i*i);
int ss = sqr_nums.size();
dp[0]=0;
for (int i = 1; i<=n; i++) {
for (int j = 0; j < ss; j++) {
if (sqr_nums[j]>i) break;
dp[i] = min(dp[i-sqr_nums[j]] + 1, dp[i]);
}
}
return dp[n];
}
};
120. Triangle Medium
类似931. Minimum Falling Path Sum
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i-1][j+1]) + dp[i][j], 还要处理边缘的case
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
for (int i=1; i<triangle.size(); i++) {
int ss = triangle[i].size();
for (int j=0; j<ss; j++) {
if (!j)
triangle[i][j] += triangle[i-1][j];
else if (j==ss-1)
triangle[i][j] += triangle[i-1][j-1];
else
triangle[i][j] += min(triangle[i-1][j],
triangle[i-1][j-1]);
}
}
return *min_element(triangle[triangle.size()-1].begin(),
triangle[triangle.size()-1].end());
}
};
1049. Last Stone Weight II Medium
474. Ones and Zeroes Medium
221. Maximal Square Medium
322. Coin Change Medium
1240. Tiling a Rectangle with the Fewest Squares Hard
174. Dungeon Game Hard
871. Minimum Number of Refueling Stops Hard
2.达到目标的方法总数dp(Distinct Ways)
Statement：Given a target find a number of distinct ways to reach the target.
Approach：Sum all possible ways to reach the current state.
routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]
70. Climbing Stairs
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n+1, 1);
for (int i=2; i<=n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
62. Unique Paths
f[i][j] = f[i][j-1]+f[i-1][j];
class Solution {
public:
int uniquePaths(int m, int n) {
// f[i][j] = f[i][j-1]+f[i-1][j];
vector<vector<int>> dp(m, vector<int>(n, 0));
dp[0][0] = 1;
for(int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (i && j)
dp[i][j] = dp[i][j-1] + dp[i-1][j];
else if (i)
dp[i][j] = dp[i-1][j];
else if (j)
dp[i][j] = dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};