资讯详情

DAY23 2026.05.13

LeetCode1143 最长公共子序列 [多维动态规划]

1. 确定dp数组以及下标的含义

​ dp[i][j]表示[0，i-1]的nums1和[0，j-1]的nums2，二者的最长公共子序列的长度

2. 确定递推公式

​ 如果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]）

3. dp数组如何初始化

​ 与空字符串比较无公共子序列，故第零行和第零列都初始化为0

4. 确定遍历顺序

​ 由递推公式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 两个字符串的删除操作，细节上有所区别

1. 确定dp数组以及下标的含义

​ dp[i][j]表示将以i-1为结尾的word1转换成以j-1为结尾的word2的最少操作次数

2. 确定递推公式

​ 两种情况：

• 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))

3. dp数组如何初始化

​ dp[i][0] = i，word1需要进行i次删除得到空字符串

​ dp[0][j] = j，word2需要进行j次删除得到空字符串

4. 确定遍历顺序

​ dp[i][j]由dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]推出，所以是从左到右，从上到下进行遍历