六、最小路径和
难度：Medium
状态：
子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的最短路径
F(i,j)：从(0,0)到达F(i,j)的最短路径
状态转移方程：
F(i,j) = min{ F(i-1,j) , F(i,j-1) } + (i,j)
初始值：
F(0,0) = (0,0) F(0,i) = F(0,i-1) + (0,i) F(i,0) = F(i-1,0) + (i,0) （i > 0）
返回结果：F(m - 1,n - 1)
class Solution { public: int minPathSum(vector<vector<int> >& grid) { if(grid.empty()) return 0; const int row = grid.size(); const int col = grid[0].size(); for(int i = 1;i < col; ++i) grid[0][i] += grid[0][i - 1]; for(int i = 1;i < row; ++i) grid[i][0] += grid[i - 1][0]; for(int i = 1; i < row; ++i) { for(int j = 1; j < col; ++j) { grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]); } } return grid[row - 1][col - 1]; } };
七、背包问题
难度：Medium
状态：F(i, j)：前i个物品放入大小为j的背包中所获得的最大价值
状态递推：
对于第i个商品，若装不下：此时的价值与前 i-1 个的价值是一样的 F(i,j) = F(i-1,j)
若可以装入：需要在装或不装中选择最大的
F(i, j) = max{ F(i-1,j), F(i-1, j - A[i]) + V[i] }
F(i-1,j): 表示不把第i个物品放入背包中， 所以价值就是前i-1个物品放入大小为j的背包的最大价值
F(i-1, j - A[i]) + V[i]：表示第i个物品放入背包中，价值增加V[i]，但需腾出A[i]的大小放第i个商品
初始化：第0行和第0列都为0，表示没有装物品时的价值都为0 F(0,j) = F(i,0) = 0
返回值：F(n,m)
class Solution { public: int backPackII(int m, vector<int>& a, vector<int>& v) { if (a.empty() || v.empty() || m <= 0) return 0; const int row = a.size() + 1; const int col = m + 1; vector<vector<int>> ret(row); for (int i = 0; i < row; ++i) { ret[i].resize(col, 0); } for (int i = 1; i < row; ++i) { for (int j = 1; j < col; ++j) { if (a[i - 1] > j) ret[i][j] = ret[i - 1][j]; else ret[i][j] = max(ret[i - 1][j], ret[i - 1][j - a[i - 1]] + v[i - 1]); } } return ret[row - 1][col - 1]; } };
优化版
每一行的结果都从上一行的结果推出，那么就可以优化空间复杂度为O(m)，从后向前推导即可
class Solution { public: int backPackII(int m, vector<int>& a, vector<int>& v) { if (a.empty() || v.empty() || m <= 0) return 0; vector<int> ret(m + 1); for (int i = 1; i < a.size() + 1; ++i) { for (int j = m; j >= 1; --j) { if (a[i - 1] <= j) ret[j] = max(ret[j], ret[j - a[i - 1]] + v[i - 1]); } } return ret[m]; } };
八、回文串分割
难度：Hard
状态：
子状态：从第0个到第1，2，3，...，n个字符组成的字符串分割成回文 需要的最小分割数
F(i): 从第0个到第i个字符组成的字符串分割成回文 需要的最小分割数
状态递推：
若从j+1到i为回文字符串，且已经知道从第1个字符到第j个字符的最小切割数，那么只需要再切一次，就可以保证 1->j ， j+1 -> i都为回文串
(j < i) && (j+1 -> i)为true的情况下，F(i) = min( F[i], F[j] + 1)
初始化：F(i) = i - 1
单个字符只需要切0次，因为单子符都为回文串，2个字符最大需要1次，3个2次......
返回值：F(n)
class Solution { public: bool isPal(string& s, int begin, int end) { while (begin < end) { if (s[begin] != s[end]) return false; ++begin; --end; } return true; } int minCut(string s) { int size = s.size(); if (size == 0 || isPal(s, 0, size - 1)) return 0; vector<int> ret(size + 1); for (int i = 1; i <= size; ++i) { ret[i] = i - 1; } for (int i = 2; i <= size; ++i) { if (isPal(s, 0, i - 1)) { ret[i] = 0; continue; } for (int j = 1; j < i; ++j) { if (isPal(s, j, i - 1)) ret[i] = min(ret[i], ret[j] + 1); } } return ret[size]; } };
上述方法两次循环时间复杂度是O(n^2)，判断回文串时间复杂度是O(n)，所以总时间复杂度为O(n^3)。对于过长的字符串，在OJ的时候会出现TLE(Time Limit Exceeded)
判断回文串的方法可以使用动态规划进行优化，使总体时间复杂度为O(n^2)
状态：
子状态：从第一个字符到第二个字符是不是回文串，第1-3，第2-5，...
F(i,j)：字符区间 [i,j] 是否为回文串
状态递推：
F(i,j)：true->{ s[i]==s[j] && F(i+1,j-1) } OR false
若字符区间首尾字符相同且在去掉区间首尾字符后字符区间仍为回文串，则原字符区间为回文串
从递推公式中可以看到第i处需要用到第i+1处的信息，所以i应该从字符串末尾遍历
初始化：F(i,j) = false
返回结果：矩阵F(n,n), 只更新一半值（i <= j），n^2 / 2
vector<vector<bool>> GetMat(string& s) { int size = s.size(); vector<vector<bool>> ret(size, vector<bool>(size, false)); for (int i = size - 1; i >= 0; --i) { for (int j = i; j < size; ++j) { if (i == j) ret[i][j] = true; else if (j == i + 1) ret[i][j] = (s[i] == s[j]) else ret[i][j] = ((s[i] == s[j]) && ret[i + 1][j - 1]); } } return ret; }
九、编辑距离
难度：Hard
状态：
子状态：word1的前1，2，3，...m个字符转换成word2的前1，2，3，...n个字符需要的编辑距离
F(i,j)：word1的前i个字符于word2的前j个字符的编辑距离
状态递推：
F(i,j) = min { F(i-1,j）+ 1，F(i,j-1) + 1，F(i-1,j-1) + (w1[i] == w2[j] ? 0 : 1) }
上式表示从删除，增加和替换操作中选择一个最小操作数
F(i-1,j)：w1[1,...,i-1]于w2[1,...,j]的编辑距离，删除w1[i]的字符--->F(i,j)
F(i,j-1)：w1[1,...,i]于w2[1,...,j-1]的编辑距离，增加一个字符--->F(i,j)
F(i-1,j-1)：w1[1,...,i-1]于w2[1,...,j-1]的编辑距离，若w1[i]与w2[j]相同，不做任何操作，编辑距离不变，若w1[i]与w2[j]不同，替换w1[i]的字符为w2[j]--->F(i,j)
初始值：初始化一定要是确定的值，如果这里不加入空串，初始值无法确定
F(i,0) = i：word与空串的编辑距离，删除操作
F(0,i) = i：空串与word的编辑距离，增加操作
返回值：返回结果：F(m,n)
class Solution { public: int minDistance(string word1, string word2) { int row = word1.size(); int col = word2.size(); vector<vector<int>> ret(row + 1, vector<int>(col + 1)); for (int i = 0; i <= col; ++i) ret[0][i] = i; for (int i = 0; i <= row; ++i) ret[i][0] = i; for (int i = 1; i <= row; ++i) { for (int j = 1; j <= col; ++j) { if (word1[i - 1] == word2[j - 1]) { ret[i][j] = min(ret[i - 1][j], ret[i][j - 1]) + 1; ret[i][j] = min(ret[i][j], ret[i - 1][j - 1]); } else { ret[i][j] = min(ret[i - 1][j], ret[i][j - 1]) + 1; ret[i][j] = min(ret[i][j], ret[i - 1][j - 1] + 1); } } } return ret[row][col]; } };
十、不同子序列
难度：Hard
状态：
子状态：S的前1,2,...,m个字符组成的字符串的子串 与T前1,2,...,n个字符组成的字符串相同的个数
F(i,j)：S[1:i]中的子串与T[1:j]相同的个数
状态递推：
当S[i] = T[j]时：
若使用S[i]匹配T[j]，则F(i,j) = F(i-1,j-1)
若不使用S[i]匹配T[j]，则问题就变为S[1:i-1]中的子串与T[1:j]相同的个数，则F(i,j) = F(i-1,j)
故，S[i] == T[j]时，F(i,j) = F(i-1,j-1) + F(i-1,j)
当S[i] != T[j]：问题退化为S[1:i-1]中的子串与T[1:j]相同的个数。S[i] != T[j]时，F(i,j) = F(i-1,j)
初始化：引入空串进行初始化
F(i,0) = 1 S的子串与空串相同的个数，只有空串与空串相同
返回值：F(m,n)
class Solution { public: int numDistinct(string S, string T) { int row = S.size(); int col = T.size(); if(row < col) return 0; if(T.empty()) return 1; vector<vector<int>> ret(row + 1, vector<int>(col + 1, 0)); ret[0][0] = 1; for(int i = 1; i <= row; ++i) { ret[i][0] = 1; for(int j = 1;j <= col; ++j) { if(S[i - 1] == T[j - 1]) ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1]; else ret[i][j] = ret[i - 1][j]; } } return ret[row][col]; } };
