算法题打卡-二维动态规划-拓冰建站

62. 不同路径

路径数量，二维dp数组的定义已经在题目中显式给出，简单。可以压缩成一维dp数组，懒，不想压了。

classSolution{public:/* dp[i][j] 到达i行j列的路径数量 */intuniquePaths(intm,intn){vector<vector<int>>dp(m,vector<int>(n,0));for(inti=0;i<m;i++)dp[i][0]=1;for(intj=0;j<n;j++)dp[0][j]=1;for(inti=1;i<m;i++){for(intj=1;j<n;j++){dp[i][j]=dp[i-1][j]+dp[i][j-1];}}returndp[m-1][n-1];}};

64. 最小路径和

没什么需要特别注意的。

classSolution{public:/* dp[i][j] 到达网格i行j列的最小数字和 */intminPathSum(vector<vector<int>>&grid){intm=grid.size(),n=grid[0].size();vector<vector<int>>dp(m,vector<int>(n,0));dp[0][0]=grid[0][0];for(inti=1;i<m;i++)dp[i][0]=grid[i][0]+dp[i-1][0];for(intj=1;j<n;j++)dp[0][j]=grid[0][j]+dp[0][j-1];for(inti=1;i<m;i++){for(intj=1;j<n;j++){intcost=grid[i][j];dp[i][j]=cost+min(dp[i-1][j],dp[i][j-1]);}}returndp[m-1][n-1];}};

1143. 最长公共子序列

本题让我对状态转移又有了新的理解：当前比较字符串abc和ab，c != b，所以最长公共子序列的结果是max(ab与ab，abc与a)。
我自己在考虑时，匹配成功的结果是dp[i][j]++，匹配不成功时，就想不到如何利用前一个状态了。
无法继续的原因是匹配后没有利用上一个状态做转移，而是粗暴地给dp[i][j]在初始值基础上去加一。当前比较c1和c2的结果已知，如果都满足，加一是对的，给谁加一？给去掉c1和c2的两字符串比较结果加一。基于这个逻辑，c1≠c2的处理逻辑就很好处理了，在（t1-c1，t2）和（t1，t2 - c2）中取更大值。

classSolution{public:/* dp[i][j]: text1在0-i，与text2在0-j的最长公共子序列长度 */intlongestCommonSubsequence(string text1,string text2){intlen1=text1.length(),len2=text2.length();vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));for(inti=1;i<=len1;i++){charc1=text1.at(i-1);for(intj=1;j<=len2;j++){charc2=text2.at(j-1);if(c1==c2)dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}returndp[len1][len2];}};

72. 编辑距离

很有趣的一道题，运用1143解法的方式很巧妙，出处参考力扣题解，这里我把自己的思考过程写下来。

对于word1 = “hosre”, word2 = “ros”，以dp[1][1]的求解为例：
dp[1][1] = "h"到"r"的距离
既然要设计状态转移，我们来看左、上、左上分别是什么：

左 dp[1][0] = “h"到”"的距离
上 dp[0][1] = ""到"r"的距离
左上 dp[0][0] = "“到”"的距离

接下来看可能的状态转移方程：

dp[1][1] = 左 + ""到"r"的距离 = 左 + 1
dp[1][1] = 上 + “h"到”"的距离 = 上 + 1
dp[1][1] = 左上 + "h"到"r"的距离 = 左上 + 1

在上述三种方式中选择最小的即可。

再看一个例子：
dp[2][2] = "ho到"ro"的距离

左 dp[2][1] = "ho"到"r"的距离
上 dp[1][2] = "h"到"ro"的距离
左上 dp[1][1] = "h"到"r"的距离

可能的状态转移方程：

dp[2][2] = 左 + ""到"o"的距离 = 左 + 1
dp[2][2] = 上 + “o"到”"的距离 = 上 + 1
dp[2][2] = 左上 + "o"到"o"的距离 = 左上 + 0

总结

dp[i][j] = 左 + ""到"c2"的距离 = 左 + 1
dp[i][j] = 上 + “c1"到”"的距离 = 上 + 1
dp[i][j] = 左上 + "c1"到"c2"的距离
- 若 c1 == c2，"c1"到"c2"的距离 = 0
- 若 c1 != c2，"c1"到"c2"的距离 = 1

dp[i][j]取上述三者最小值。

classSolution{public:/* dp[i][j]：将word1 [0,i)转换为word2 [0,j)需要的最少操作数 */intminDistance(string word1,string word2){intlen1=word1.length(),len2=word2.length();vector<vector<int>>dp(len1+1,vector<int>(len2+1,0));for(inti=0;i<=len1;i++)dp[i][0]=i;for(intj=0;j<=len2;j++)dp[0][j]=j;for(inti=1;i<=len1;i++){charc1=word1.at(i-1);for(intj=1;j<=len2;j++){charc2=word2.at(j-1);intleft=dp[i][j-1]+1;intup=dp[i-1][j]+1;intleft_up=dp[i-1][j-1];if(c1!=c2)left_up+=1;dp[i][j]=min(left_up,min(left,up));}}returndp[len1][len2];}};