09｜子序列问题：详解重要的一大类动态规划问题

空间复杂度的压缩状态，dp[i][j]中的j只有两种状态，当前和前一个，使用j%2和j-1%2就可以在两者之间切换。i不可以压缩，因为内层每一轮循环，都要用到之前所有行的两个列状态，这两个列状态是只之前推到出的，不是本轮内层循环推到出的。 int getLongestCommonSubsequence(String text1, String text2) { int m = text1.length(), n = text2.length(); int[][] dp = new int[m + 1][2]; for (int[] row: dp) { Arrays.fill(row, 0); } for (int j = 1; j <= n; j++) { int a = j % 2; int b = (j - 1) % 2; for (int i = 1; i <= m; i++) { if (text2.charAt(j - 1) == text1.charAt(i - 1)) { dp[i][a] = dp[i - 1][b] + 1; } else { dp[i][a] = Math.max(dp[i - 1][a], dp[i][b]); } } } return dp[m][n%2]; }

又学到了新知识，开心。 老师的第一个状态转移方程与实际代码不匹配，代码中是正确的。 dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); 而dp方程是 dp[i][j] = Math.max(dp[i+1][j], dp[i][j+1]);

if(text2[j-1]==text1[i-1])，这个不对吧，不是应该判定text2[j]==text1[i]吗？这里不太懂为什么减1，麻烦老师解说一下

老师您好，在第二个问题求解最长公共子序列中，开始定义的dp[i][j]表示text1[0][i]与text2[0][j]的最长公共子序列，但是实际代码中返回的是dp[m][n]，这与预定义的不符合吧,text1[m]与text2[n]应该越界了吧． 而且我们定义dp数组时，也是添了一行一列，不如定义dop[i][j]为text1的前i个字符和text2的前j个字符所对应的最长公共子序列，既然dp添了一行一列，那么text1与text2也在开头添一个字符，这样所有的下标都是从1开始，会不会好一点． 在处理动规问题时，下标从0开始还是从1开始，我觉得对我来说也是一个很大的坑，容易陷进去，希望老师后续可以讲一下这一点的注意事项．

在最长公共子序列的画的表中的dp[2][4]不应该是2嘛，ad和abcde中最长的ad都只有2，怎么来的3啊老师，是错了还是什么

讲算法还是视频形式好

在最长回文子序列问题中，对于dp[i][j], 当i>j时，都是无效子串吧，值都为0，遍历的时候i是不是只要从i-2开始遍历就行

for (int i = n-1; i >= 0; i--) { for (int j = i+1; j < n; j++) ，这两个for循环，我有点看不懂？？？

当s[i]!=s[j]，为什么要向前后一步呢？为什么最终结果会在左上角获取？

可以空间优化，只需要一维数组。划好状态矩阵，可知下一行状态就是上一行和左边的数据分析后的结果，所以需要临时变量存储左上角的状态。具体代码如下。 public int longestCommonSubsequence(String text1, String text2) { int n1 = text1.length(); int n2 = text2.length(); int[] dp = new int[n1 + 1]; for (int i = 0; i < n1 + 1; i++) { dp[i] = 0; } for (int i = 1; i < n2 + 1; i++) { int temp = 0; int cp = 0; for (int j = 1; j < n1 + 1; j++) { if (text1.charAt(j - 1) == text2.charAt(i - 1)) { temp = cp + 1; } else { temp = Math.max(dp[j - 1], dp[j]); } cp = dp[j]; dp[j] = temp; } } return dp[n1]; }