DP+字符串的问题。。。

Question

LeetCode周赛卡在第四题。。。
https://leetcode-cn.com/problems/shortest-common-supersequence/
参考大神java的代码：
class Solu1092 {
public String shortestCommonSupersequence(String str1, String str2) {
int len1=str1.length(),len2=str2.length();
int[][] dp=new int[len1+1][len2+1];
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(str1.charAt(i-1)==str2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
StringBuilder sb=new StringBuilder();
for(int i=len1,j=len2;i>0||j>0;){
if(i<=0){
sb.append(str2.charAt(–j));
}else if(j<=0){
sb.append(str1.charAt(–i));
}else if(dp[i][j]>dp[i-1][j]&&dp[i][j]>dp[i][j-1]){
sb.append(str1.charAt(–i));
–j;
}else if(dp[i][j]>dp[i-1][j]){
sb.append(str2.charAt(–j));
}else{
sb.append(str1.charAt(–i));
}
}
return sb.reverse().toString();
}

先建立了一个矩阵，然后逆推。在idea里debug了一下，结果确实是对的。但是实在想不通他这个DP矩阵存的东西代表什么意思。。。
另外到现在的刷题过程中，碰到的dp问题大多能解，只要发觉递推得关系就行，反而是一些字符串、数字问题无从下手。。。不知咋办。。

Answer 1

liuyubobobo 2019-06-16 18:15:08

这个dp的内容求得就是LCS啊：）LCS（最长公共子序列）在这个课程中有过介绍，再回顾一下？

https://coding.imooc.com/lesson/82.html#mid=2987

求出LCS后，反推字符串的过程，其实就是看LCS的这个表示如何推出来的。

对于在LCS中的字符，也就是 dp[i][j]>dp[i-1][j]&&dp[i][j]>dp[i][j-1]的情况，因为对应dp表的计算，是dp[i][j]=dp[i-1][j-1]+1，这个字符只添加一次。

否则，对于不再LCS中的字符，也就是dp[i][j]>dp[i-1][j]或者dp[i][j]>dp[i][j-1]的情况，因为对应dp表的计算，是dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])，把相应字符串(atr1或者str2)中的字符添加进去：）

对于dp表的分析，在这个课程的9-9，我也简单提及过（还是上面的链接，9-9小节：https://coding.imooc.com/lesson/82.html#mid=2987），并且基于背包问题举了例子。在明确这个问题是LCS问题后，建议再理解一下LCS的dp表和这个结果之间的关系：）

继续加油！：）

• 提问者 慕桂英雄 #1

  原来课上都有，捂脸，谢谢波波老师！！

• 提问者 慕桂英雄 #2

  非常感谢！