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;
        else
        return 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;
                else
                dp[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;
                else
                dp[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];
                else
                dp[i+1][j+1]=min(min(dp[i][j+1],dp[i+1][j]),dp[i][j])+1;
            }
        }
        return dp[n1][n2];
    }
};

加油！动态规划！