Day49 | 动态规划 ：线性DP 判断子序列&&两个字符串的删除操作

动态规划应该如何学习？-CSDN博客

动态规划学习：

1.思考回溯法（深度优先遍历）怎么写

注意要画树形结构图

2.转成记忆化搜索

看哪些地方是重复计算的，怎么用记忆化搜索给顶替掉这些重复计算

3.把记忆化搜索翻译成动态规划

基本就是1:1转换

392.判断子序列

392. 判断子序列 - 力扣（LeetCode）

思路分析（子问题）：

就是昨天的编辑距离的删除操作Day48 | 动态规划 ：线性DP 编辑距离-CSDN博客

dfs(x,y)就是s的前x个字符是不是t的前y个字符的子序列，是返回true，不是返回false

x为s的下标，y为t的下标

还是看选或不选s[x]和t[y]

1.如果s[x]==t[y]

那就选s[x]和t[y]

返回dfs(x-1,y-1)，继续递归下面的，即

1
dfs(x,y)=dfs(x-1,y-1)

也可以理解为当前的s[x]和t[y]对结果没有影响

2.如果s[x]!=t[y]

那就是删除掉t[y]看t剩下的部分包不包含s

1
dfs(x,y)=dfs(x,y-1)

递归边界

如果s为空串，那一定是t的子序列，返回true

如果t为空串，那s不管怎么样都不会是t的子序列，返回false

1.回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool dfs(int i,int j,string &s,string &t)
    {
        if(i<0)
            return true;
        if(j<0)
            return false;
        if(s[i]==t[j])
            return dfs(i-1,j-1,s,t);
        else
            return dfs(i,j-1,s,t);
    }
    bool isSubsequence(string s, string t) {
        return dfs(s.size()-1,t.size()-1,s,t);
    }
};

2.记忆化搜索

就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool dfs(int i,int j,string &s,string &t,vector<vector<int>> &dp)
    {
        if(i<0)
            return true;
        if(j<0)
            return false;
        if(dp[i][j]!=-1)
            return dp[i][j];
        if(s[i]==t[j])
            return dp[i][j]=dfs(i-1,j-1,s,t,dp);
        else
            return dp[i][j]=dfs(i,j-1,s,t,dp);
    }
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size(),vector<int>(t.size(),-1));
        return dfs(s.size()-1,t.size()-1,s,t,dp);
    }
};

3.动态规划

注意我们的i=0和j=0是表示的dfs中i<0和j<0非法的状态，即s为空串或者t为空串，对应的是递归边界

所以dp数组的下标从1开始记录答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<bool>> dp(s.size()+1,vector<bool>(t.size()+1,false));
        for(int i=0;i<=t.size();i++)
            dp[0][i]=true;
        for(int i=0;i<s.size();i++)
            for(int j=0;j<t.size();j++)
                if(s[i]==t[j])
                    dp[i+1][j+1]=dp[i][j];
                else    
                    dp[i+1][j+1]=dp[i+1][j];
        return dp[s.size()][t.size()];
    }
};

583.两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（LeetCode）

思路分析（子问题）：

就是昨天的编辑距离的删除操作Day48 | 动态规划 ：线性DP 编辑距离-CSDN博客

1
2
3
4
5
6
7
8
//相等不用删		
if(s[i]==t[j])
	return dfs(i-1,j-1,s,t);
//不相等
else
	return min(dfs(i-1,j,s,t),dfs(i,j-1,s,t))+1;
//               删s的            删t的
//两个里面搞一个最小值最后再把删除这一步的步数1加上搞定

仅仅是去掉了替换操作，剩下的代码都一样的，这里不做过多的解释了

1.回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int dfs(int i,int j,string& s,string &t)
    {
        if(i<0)
            return j+1;
        if(j<0)
            return i+1;
        if(s[i]==t[j])
            return dfs(i-1,j-1,s,t);
        else
            return min(dfs(i-1,j,s,t),dfs(i,j-1,s,t))+1;
    }
    int minDistance(string word1, string word2) {
        return dfs(word1.size()-1,word2.size()-1,word1,word2);        
    }
};

2.记忆化搜索

就是搞一个哈希表dp，全都初始化为-1，每次返回前给哈希表dp赋值，碰到不是-1的那就是算过的，那就直接返回计算过的结果，不需要再次递归了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int dfs(int i,int j,string& s,string &t,vector<vector<int>> &dp)
    {
        if(i<0)
            return j+1;
        if(j<0)
            return i+1;
        if(dp[i][j]!=-1)
            return dp[i][j];
        if(s[i]==t[j])
            return dp[i][j]=dfs(i-1,j-1,s,t,dp);
        else
            return dp[i][j]=min(dfs(i-1,j,s,t,dp),dfs(i,j-1,s,t,dp))+1;
    }
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size(),vector<int>(word2.size(),-1));
        return dfs(word1.size()-1,word2.size()-1,word1,word2,dp);        
    }
};

3.动态规划

注意我们的i=0和j=0是表示的dfs中i<0和j<0非法的状态，即s为空串或者t为空串，对应的是递归边界

所以dp数组的下标从1开始记录答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i=0;i<=word2.size();i++)
            dp[0][i]=i;
        for(int i=0;i<=word1.size();i++)
            dp[i][0]=i;
        for(int i=0;i<word1.size();i++)
            for(int j=0;j<word2.size();j++)
                if(word1[i]==word2[j])
                    dp[i+1][j+1]=dp[i][j];
                else
                    dp[i+1][j+1]=min(dp[i+1][j],dp[i][j+1])+1;
        return dp[word1.size()][word2.size()];        
    }
};