抱佛脚一时爽，一直抱佛脚一直爽！这篇文章总结常见的动态规划问题~
参考链接：leetcode 剑指offer
概述
- 如果动态规划方程只需用到有限个变量，则可以不用动态规划数组，而是用几个变量记录它们
- 动态规划和递归+记忆数组本质上是一样的
跳格子问题
不记录体力值；返回是否能到最后一格（lc55）
- 原始dp是f[i]表示能否跳到i；f[i+1]=for j in 0~i: f[j] && nums[j] >= i - j；现在优化为用curMax记录最大的nums[j] + j
- [0] 返回 true
bool canJump(vector<int>& nums){
int n=nums.size();
if(!n)return true;
int curMax=nums[0];
bool result=false;
for(int i=1;i<n; ++i){
if(curMax>=i){
curMax=max(curMax,nums[i]+i);
}else{
nums[i]=-i; // 处理第i位置无法到达的情况
}
}
return curMax>=n-1;
}
记录体力值；返回最大剩余体力
不记录体力值；返回最少需要跳跃的次数（lc45）
int jump(vector<int>& nums) {
int res = 0, n = nums.size(), i = 0, cur = 0;
while (cur < n - 1) {
++res;
int pre = cur;
for (; i <= pre; ++i) {
cur = max(cur, i + nums[i]);
}
if (pre == cur) return -1; // May not need this，因为题目已知肯定能跳到最后
}
return res;
}
其他题目
凑到amount最少需要的硬币数（lc322）
- dp[i]记录凑到i最少需要的硬币数，dp[i] = min(dp[i - coin] + 1);
剪绳子（jz68）
class Solution {
public int cutRope(int number) {
if (number <= 1) return -1;
if (number == 2) return 1;
if (number == 3) return 2;
int[] res = new int[number + 1];
res[0] = 0;
res[1] = 1;
res[2] = 2;
res[3] = 3;
for (int i = 4; i <= number; ++i) {
int max = -1;
for (int j = 1; j <= i / 2; ++j) {
max = Math.max(max, res[i - j] * res[j]);
}
res[i] = max;
}
return res[number];
}
};
编辑距离（lc72）
- 思路：当 word1[i] == word2[j] 时，dp[i][j] = dp[i - 1][j - 1]，其他情况时，dp[i][j] 是其左，左上，上的三个值中的最小值加1，其实这里的左，上，和左上，分别对应的增加，删除，修改操作
int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for (int i = 0; i <= m; ++i) dp[i][0] = i;
for (int i = 0; i <= n; ++i) dp[0][i] = i;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
}
}
}
return dp[m][n];
}
最大正方形（lc221）
- dp[i][j] 表示到达 (i, j) 位置所能组成的最大正方形的边长
- 对于任意一点 dp[i][j]，若当前 (i, j) 位置为0，则dp[i][j]为0
- 否则，该点是正方形的右下角；左边，上边，和左上边这三个位置的dp值 suppose 都应该算好的。此时要看 dp[i-1][j-1], dp[i][j-1]，和 dp[i-1][j] 这三个位置，我们找其中最小的值，并加上1，就是 dp[i][j] 的当前值了
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size(), res = 0;
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i == 0 || j == 0) dp[i][j] = matrix[i][j] - '0';
else if (matrix[i][j] == '1') {
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1;
}
res = max(res, dp[i][j]);
}
}
return res * res;
}
最小路径和（lc64）
- 因为到达当前位置 (i, j) 只有两种情况，要么从上方 (i-1, j) 过来，要么从左边 (i, j-1) 过来，我们选择 dp 值较小的那个路径，即比较 dp[i-1][j] 和 dp[i][j-1]，将其中的较小值加上当前的数字 grid[i][j]，就是当前位置的 dp 值了
- 因为每次只需要借鉴两个值，所以用两个变量记住它们即可
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty() || grid[0].empty()) return 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (i == 0 && j == 0) continue;
int up = (i == 0) ? INT_MAX : grid[i - 1][j];
int left = (j == 0) ? INT_MAX : grid[i][j - 1];
grid[i][j] += min(up, left);
}
}
return grid.back().back();
}
解码方法（lc91）
- 法一：对已有的结果集，把当前数attach到最后一个结果后面，或者把当前数作为一个新数加入结果集；返回结果集大小
- 法二：取s的第一位，求后面的数的numDecodings结果；取s的前两位，求后面的数的numDecodings结果
- 法三：dp；dp[i]表示前i位能解码的数量
int numDecodings(string s) {
if (s.empty() || s[0] == '0') return 0;
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int i = 1; i < dp.size(); ++i) {
dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1];
if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp.back();
}
从矩阵左上角到右下角路径数（lc62）
- 法一：dp；f[i][j] = f[i - 1][j] + f[i][j - 1]
- 法二：相当于机器人总共走了 m + n - 2步，其中 m - 1 步向右走，n - 1 步向下走，那么总共不同的方法个数= C(m+n-2 m-1)
三角形路径和（lc120）
- 法一：深搜，会超时
- 法二：dp
- 思路：dp[i][j]表示到达triangle[i][j]的最小路径和：dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])
- 改进：不用额外的dp数组，直接把和累加到triangle中
int minimumTotal(vector<vector<int>>& triangle) {
if (!triangle.size() || !triangle[0].size()) return 0;
for (int i = 1; i < triangle.size(); ++i) {
for (int j = 0; j < triangle[i].size(); ++j) {
if (j == 0) triangle[i][j] += triangle[i - 1][j];
else if (j == triangle[i].size() - 1) triangle[i][j] += triangle[i - 1][j - 1];
else triangle[i][j] += min(triangle[i - 1][j], triangle[i - 1][j - 1]);
}
}
int res = INT_MAX;
for (int i = 0; i < triangle.back().size(); ++i) {
res = min(res, triangle.back()[i]);
}
return res;
}
int minimumTotal(vector<vector<int>>& triangle) {
vector<int> dp(triangle.back());
for (int i = (int)triangle.size() - 2; i >= 0; --i) {
for (int j = 0; j <= i; ++j) {
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
}
}
return dp[0];
}
交叉字符串（lc97）
- dp[i][j]表示s3的前i+j位是否由s1的前i位和s2的前j位交叉而成
bool isInterleave(string s1, string s2, string s3) {
int len1 = s1.size(), len2 = s2.size(), len3 = s3.size();
if (len3 != len1 + len2) return false;
if (!len1) return s2 == s3;
if (!len2) return s1 == s3;
vector<vector<bool>> dp(len1 + 1, vector<bool>(len2 + 1, false));
dp[0][0] = true;
for (int j = 1; j <= len2; ++j) dp[0][j] = (s3.substr(0, j) == s2.substr(0, j));
for (int i = 1; i <= len1; ++i) dp[i][0] = (s3.substr(0, i) == s1.substr(0, i));
for (int i = 1; i <= len1; ++i) {
for (int j = 1; j <= len2; ++j) {
if (s3[i + j - 1] == s1[i - 1]) dp[i][j] = dp[i - 1][j];
if (s3[i + j - 1] == s2[j - 1]) dp[i][j] = dp[i][j] || dp[i][j - 1];
}
}
return dp[len1][len2];
}
打家劫舍（lc198）
- dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i]
求两个正整数数组的最长公共子串
- dp[i][j]为以A[i]和B[j]结尾的最长公共子串
俄罗斯套娃信封问题（lc354）
- 给所有的信封按从小到大排序：首先根据宽度从小到大排，如果宽度相同，那么高度小的再前面，这是STL里面sort的默认排法；对于每一个信封，遍历其前面所有的信封，如果当前信封的长和宽都比前面那个信封的大，那么dp[i] = max(dp[i], dp[j] + 1)；每遍历完一个信封，更新res
