LeetCode 1143 https://leetcode.cn/problems/longest-common-subsequence/description/ 难度：中等 LCS 线性 DP 问题，状态转移方程如下： if (s[i] == t[j]) { f[i + 1][j + 1] = f[i][j] + 1; } else { f[i + 1][j + 1] = max(f[i + 1][j], f[i][j + 1]); } 时间复杂度：O(nm)。 空间复杂度：O(nm)。 ...
LeetCode 72 https://leetcode.cn/problems/edit-distance/description/ 难度：中等 这是线性 DP 的经典题目，类似 LeetCode 1143 最长公共子序列。 状态转移方程为： //word1[i] == word2[j] f[i + 1][j + 1] = f[i][j]; //word1[i] != word2[j] f[i + 1][j + 1] = min({f[i + 1][j], f[i][j + 1], f[i][j]}) + 1; 在不相等时，三种情况分别对应插入，删除，替换的情况。 此外，还要注意数组的初始化操作。 f[i + 1][0] = i + 1; f[0][j + 1] = j + 1; 时间复杂度：O(nm)，其中 n 为 word1 的长度，m 为 word2 的长度。 空间复杂度：O(nm)。 ...