leetcode 115. Distinct Subsequences 简单DP变形+一个必须要学会的DP问题

小咪咪 2022-06-08 04:16 143阅读 0赞

Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

Here is an example:  
S = “rabbbit”, T = “rabbit”

Return 3.

题意很简答，就是类似LCS等等问题的一个DP问题。

这个问题是典型的DP解法，类似LCS 最长子序列的解法，定义二维数组dp\[i\]\[j\]为字符串s(0,i)变换到t(0,j)的变换方法。如果S\[i\]==T\[j\]，那么dp\[i\]\[j\] = dp\[i-1\]\[j-1\] + dp\[i-1\]\[j\]。意思是：如果当前S\[i\]==T\[j\]，那么当前这个字母即可以保留也可以抛弃，所以变换方法等于保留这个字母的变换方法加上不用这个字母的变换方法。如果S\[i\]!=T\[i\]，那么dp\[i\]\[j\] = dp\[i-1\]\[j\]，意思是如果当前字符不等，那么就只能抛弃当前这个字符。 递归公式中用到的dp\[0\]\[0\] = 1，dp\[i\]\[0\] = 0（把任意一个字符串变换为一个空串只有一个方法）

代码如下：

/*
     * 这个问题是典型的DP解法，类似LCS 最长子序列的解法
     * 定义二维数组dp[i][j]为字符串s(0,i)变换到t(0,j)的变换方法。
     * 
     * 如果S[i]==T[j]，那么dp[i][j] = dp[i-1][j-1] + dp[i-1][j]。
     * 意思是：如果当前S[i]==T[j]，那么当前这个字母即可以保留也可以抛弃，
     * 所以变换方法等于保留这个字母的变换方法加上不用这个字母的变换方法。
     * 
     * 如果S[i]!=T[i]，那么dp[i][j] = dp[i-1][j]，意思是如果当前字符不等，那么就只能抛弃当前这个字符。
     * 
     * 递归公式中用到的dp[0][0] = 1，dp[i][0] = 0（把任意一个字符串变换为一个空串只有一个方法） 
     * */
    public class Solution 
    {
        public int numDistinct(String s, String t) 
        {
        
            if( s == null || t == null || s.length() < t.length())
                return 0;
    
            int dp[][] = new int [s.length()+1][t.length()+1];
            dp[0][0]=1;
            for(int i=1;i<s.length()+1;i++)
                dp[i][0] = 1;
            for(int i=1;i<t.length()+1;i++)
                dp[0][i] = 0;
            for(int i=1;i<dp.length;i++)
            {
        
                for(int j=1;j<dp[0].length;j++)
                {
        
                    if(s.charAt(i-1) == t.charAt(j-1))
                        dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                    else
                        dp[i][j] = dp[i-1][j];
                }
            }
            return dp[s.length()][t.length()];
        }
    }

下面是C++的做法，**当你遇到字符串的匹配问题的时候就该自然而然的想到使用DP动态规划来解决**，

下面就是DP动态规划来解决，

代码如下：

#include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int numDistinct(string s, string t) 
        {
            vector<vector<int>> dp(s.length() + 1, vector<int>(t.length() + 1, 0));
            dp[0][0] = 1;
            for (int i = 1; i <= s.length(); i++)
                dp[i][0] = 1;
            for (int i = 1; i <= t.length(); i++)
                dp[0][i] = 0;
    
            for (int i = 1; i <= s.length(); i++)
            {
                for (int j = 1; j <= t.length(); j++)
                {
                    if (s[i - 1] == t[j - 1])
                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                    else
                        dp[i][j] = dp[i - 1][j];
                }
            }
            return dp[s.length()][t.length()];
        }
    };