当前位置：首页 > article >正文

DP子序列问题

article 2024/9/21 11:06:19

1.Leetcode.392. 判断子序列
最朴素的题目。

对于此题使用f[i][j]代表s的前i-1和t的前j-1匹配上的字符串长度，那么只要是最后的f[s.size()][t.size()] == s.size()，那么就代表着s是t的子序列。

之后解决状态转移方程的问题：

当s[i-1] == t[j-1]时，f[i][j] = f[i-1][j-1] + 1，意义为当前s[i-1]和t[j-1]匹配上了，那么就是说我们可以在s[i-2]和t[j-2]匹配或者没匹配上的基础上加上1个长度，如果这里不好理解就请结合另一个方程一起理解。
当s[i-1] != t[j-1]时，f[i][j] = f[i][j-1]，意义为当没有匹配上的时候，我们就可以直接将上一层匹配上或者没匹配上的状态拿过来，然后继续按住s的第i-1个字符去往后搜t的下一个字符。

结合在一起理解，在s的第i-1个字符一直无法匹配上的时候，我们维护的f[i][j]就代表着s[i-1]和t[j-1]没有匹配上的状态，同时f[i][j]这个状态也继承了前面s[i-2]和t[j-2]匹配上或者没匹配上的状态f[i-1][j-1]，是一种递推的关系。

这是个很难理解的过程，可以进行画图理解。

CODE

int dp[110][10000 + 5] = {0};
        for(int i = 1;i <= s.size();i++){
            for(int j = 1;j <= t.size();j++){
                if(s[i-1] == t[j-1])dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = dp[i][j-1];
            }
        }
        if(dp[s.size()][t.size()] == s.size())return true;
        else return false;

2.Leetcode.115. 不同的子序列
加强版，需要我们对能够匹配出来的子序列的个数进行计数。

使用f[i][j]代表s的前i-1个字符在取t的前j-1个字符时能够计算的子序列个数的最大值。

在s[i-1] == t[j-1]的时候，f[i][j] = f[i-1][j-1] + f[i][j-1]
在s[i-1] != t[j-1]的时候，f[i][j] = f[i][j-1]

在s[i-1] == t[j-1]的时候，我们不能够仅仅使其从上一个状态加1了，因为现在我们需要计数，而不是计算长度。

int f[1010][1010] = {0};
        int mod = 1e9 + 7;
        for(int i = 0;i <= s.size();i++)f[0][i] = 1;
        for(int i = 1;i <= t.size();i++){
            for(int j = 1;j <= s.size();j++){
                if(s[j-1] == t[i-1])f[i][j] = f[i-1][j-1] + f[i][j-1];
                else f[i][j] = f[i][j-1];
                f[i][j]%=mod;
            }
        }
        return f[t.size()][s.size()];