115.leetcode Distinct Subsequences(hard)[动态规划]

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

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

.

题目的含义是要求T成为S的子串的形成方式的个数。组成动态规划状态数组L[t.length()+1][s.length()+1].

class Solution {
public:
    int numDistinct(string s, string t) {
        if(s.length()<t.length()||t.length()==0||s.length()==0) return 0;
        int n = s.length(),m = t.length();
        int L[m+1][n+1];
        for(int i=0;i<=m;i++)
            for(int j=0;j<=n;j++)
              L[i][j] = 0;
        for(int j=0;j<=n;j++)
              L[0][j] = 1;
        for(int i=1;i<=m;i++)
        {
            for(int j = i; j<=n;j++)
            {
                if(s[j-1] == t[i-1])
                {
                     L[i][j] = L[i-1][j-1]+L[i][j-1];
                }else
                     L[i][j] = L[i][j-1];
                
            }
        
        }
        return L[m][n];
    }                                                                                                                                          
};