webmin2020-10-03空间复杂度的压缩状态，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]; }作者回复: 没有问题，正确。顶上去，赞。
6
我来也2020-10-07又学到了新知识，开心。 老师的第一个状态转移方程与实际代码不匹配，代码中是正确的。 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]);作者回复: 的确状态转移方程不一致，已修正。感谢反馈。
4
振兴2021-10-08if(text2[j-1]==text1[i-1])，这个不对吧，不是应该判定text2[j]==text1[i]吗？这里不太懂为什么减1，麻烦老师解说一下作者回复: 因为0是一个空状态，遍历是[1,i]和[1,j]。所以实际比较的时候在索引上都需要减去1。
2
群2020-10-02老师您好，在第二个问题求解最长公共子序列中，开始定义的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开始，我觉得对我来说也是一个很大的坑，容易陷进去，希望老师后续可以讲一下这一点的注意事项．作者回复: 你说的对。 改成这样比较容易理解： text1[i-1] == text2[j-1] text1[i-1] != text2[j-1]
1
绘世浮夸 つ2022-03-02在最长公共子序列的画的表中的dp[2][4]不应该是2嘛，ad和abcde中最长的ad都只有2，怎么来的3啊老师，是错了还是什么作者回复: 文中的确是说这里dp[2][4]的值是2，然后dp[3][5]的值是3，可以再仔细看一下。
Sam Fu
2021-10-25讲算法还是视频形式好作者回复: 以后会考虑通过更加丰富的方式来讲解算法。
共 2 条评论- Shine2021-05-17在最长回文子序列问题中，对于dp[i][j], 当i>j时，都是无效子串吧，值都为0，遍历的时候i是不是只要从i-2开始遍历就行
作者回复: 这里j应该从i+1开始遍历。
Geek_531e372021-04-21for (int i = n-1; i >= 0; i--) { for (int j = i+1; j < n; j++) ，这两个for循环，我有点看不懂？？？作者回复: 要求解此问题，从我们构建出来的状态转移方程可以看出，其包含了两个状态，在正文中可以看到我们最终构建的备忘录是二维的，因此为了能够到达所有状态的计算位，我们需要两层for循环来进行遍历、计算。
- Geek_531e372021-04-21当s[i]!=s[j]，为什么要向前后一步呢？为什么最终结果会在左上角获取？
作者回复: 最终结果在右上角，其原因在于备忘录的定义，以及计算方向的设计问题。
猫头鹰爱拿铁2020-12-03可以空间优化，只需要一维数组。划好状态矩阵，可知下一行状态就是上一行和左边的数据分析后的结果，所以需要临时变量存储左上角的状态。具体代码如下。 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]; }作者回复: 没有问题。顶上去！