Leetcode-115. 不同的子序列

发表于 分类于 阅读次数：

题目：https://leetcode-cn.com/problems/distinct-subsequences/

解法1：动态规划

t为目标字符串，s为查找字符串

思路：

1.dp[i][j]表示t的前i字符串与s的前j字符串能形成符合要求的不同子序列的个数

2.dp[0][j]=1;即t为空字符串时的情况

3.状态转移方程：

​ s[j]!=t[i]时,dp[i][j]=dp[i][j-1]，即当前最多子序列个数，与j-1时的子序列个数相同

​ s[j]=t[i]时,dp[i][j]=dp[i][j-1]+dp[i-1][j-1]，即当前最多子序列个数，由j-1时子序列个数和s，t各减少一个字符的子序列个数组成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.length(),m=t.length();
        vector<vector<long long>> dp(m+1,vector<long long>(n+1,0));
        for(int i=0;i<=n;i++)
        {
            dp[0][i]=1;
        }
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dp[i][j]=dp[i][j-1];
                if(s[j-1]==t[i-1])
                    dp[i][j]+=dp[i-1][j-1];
            }
        }
        return dp[m][n];
    }
};