leetcode75【经典动态规划】之：最长公共子序列

又来二刷这道动态规划啦（好久没写动态规划了hh）

思路和代码是借鉴灵神的！太牛啦！最长公共子序列 编辑距离【基础算法精讲 19】_哔哩哔哩_bilibili

灵神在视频里提到两个问题：

1、s[i]=t[j]时，是否需要考虑dfs(i-1,j)和dfs(i,j-1)?

2、s[i]不=t[j]时，是否需要考虑dfs(i-1,j-1)?

回答：

1、s[i]=t[j]时，dfs(i-1,j)和dfs(i,j-1)不会优于dfs(i,j)和dfs(i-1,j-1)+1，故不需要考虑

2、s[i]=t[j]时，dfs(i-1,j)和dfs(i,j-1)包括dfs(i-1,j-1)，故不需要考虑

值得动手思考推导一下。

方法一：回溯

class Solution {
public:int dfs(string text1, string text2,int i,int j){if(i<0||j<0)return 0;if(text1[i]==text2[j])return dfs(text1,text2,i-1,j-1)+1;elsereturn max(dfs(text1,text2,i-1,j),dfs(text1,text2,i,j-1));}int longestCommonSubsequence(string text1, string text2) {if(text1.size()<=0)return 0;if(text2.size()<=0)return 0;int n1=text1.size(),n2=text2.size();return dfs(text1,text2,n1-1,n2-1);}
};

 方法二：动态规划

先贴一个错误写法hh

for(int i=0;i<n1;i++){for(int j=0;j<n2;j++){if(text1[i]==text2[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}

为啥错了？

because下标会有-1，报错。所以把下标都+1.

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int n1=text1.size(),n2=text2.size();vector<vector<int>>dp(n1+1,vector<int>(n2+1));for(int i=0;i<n1;i++){for(int j=0;j<n2;j++){if(text1[i]==text2[j])dp[i+1][j+1]=dp[i][j]+1;elsedp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);}}return dp[n1][n2];}
};

还有一题动态规划，有些细节区别，一并记录。

上一题中，考虑两字符串长度为0的情况，返回最长子序列为0就好了。

这一题有变化，一个字符串长度为0，意味着删除另一个字符串，需要返回另一个字符串的长度。因此，初始化是必须的。

代码：

class Solution {
public:int minDistance(string word1, string word2) {int dp[501][501];int n1=word1.size(),n2=word2.size();for(int i=0;i<n1;i++){dp[i+1][0]=i+1;}for(int i=0;i<n2;i++){dp[0][i+1]=i+1;}     //必须初始化for(int i=0;i<n1;i++){for(int j=0;j<n2;j++){if(word1[i]==word2[j])dp[i+1][j+1]=dp[i][j];elsedp[i+1][j+1]=min(min(dp[i][j+1],dp[i+1][j]),dp[i][j])+1;}}return dp[n1][n2];}
};

加油！动态规划！