DAY23 2026.05.13
LeetCode1143 最长公共子序列 [多维动态规划]
- 确定dp数组以及下标的含义
dp[i][j]表示[0，i-1]的nums1和[0，j-1]的nums2，二者的最长公共子序列的长度
- 确定递推公式
如果nums1[i-1] == nums2[j-1]，那么dp[i][j] = dp[i-1][j-1] + 1
如果nums1[i-1] != nums2[j-1]，那么dp[i][j] = Math.max(dp[i-1][j]，dp[i][j-1]）
- dp数组如何初始化
与空字符串比较无公共子序列，故第零行和第零列都初始化为0
- 确定遍历顺序
由递推公式dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]得出，故两层for循环都是从1开始顺序遍历到nums1.length/nums2.length
LeetCode72 编辑距离 [多维动态规划]
本题是要求从word1通过增删改的最少操作数得到word2，对word2进行增相当于对word1进行删，对word2进行改相当于对word1进行改，对word2进行删相当于对word1进行增，所以大致思路是类似于LeetCode583 两个字符串的删除操作，细节上有所区别
- 确定dp数组以及下标的含义
dp[i][j]表示将以i-1为结尾的word1转换成以j-1为结尾的word2的最少操作次数
- 确定递推公式
两种情况：
-
word1[i-1] == word2[j-1]时，word1的i-1处字符与word2的j-1处字符对相同化处理无影响，所以可以不考虑这两个元素，dp[i][j] = dp[i-1][j-1]
-
word1[i-1] != word2[j-1]时，要考虑这两个元素，分成三部分（改：w1改成w2、删：w1删w2不删、增：w1不删w2删）模拟，分别进行删减，dp[i][j] = Math.min(dp[i-1][j-1] + 1，Math.min(dp[i-1][j] + 1，dp[i][j-1] + 1))
- dp数组如何初始化
dp[i][0] = i，word1需要进行i次删除得到空字符串
dp[0][j] = j，word2需要进行j次删除得到空字符串
- 确定遍历顺序
dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]推出，所以是从左到右，从上到下进行遍历