首页 > 动态规划 > 线性DP > LeetCode-Distinct Subsequences[动态规划]
2014
11-19

LeetCode-Distinct Subsequences[动态规划]

Distinct Subsequences

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.

标签: Dynamic Programming String
分析

设状态为$f(i,j)$,表示{T[0,j]}在{S[0,i]}里出现的次数。首先,无论{S[i]}和{T[j]}是否相等,若不使用{S[i]},则$f(i,j)=f(i-1,j)$;若{S[i]==T[j]},则可以使用{S[i]},此时$f(i,j)=f(i-1,j)+f(i-1, j-1)$。

代码1

// LeetCode, Distinct Subsequences
// 二维动规+滚动数组
// 时间复杂度O(m*n),空间复杂度O(n)
class Solution {
public:
    int numDistinct(const string &S, const string &T) {
        vector<int> f(T.size() + 1);
        f[0] = 1;
        for (int i = 0; i < S.size(); ++i) {
            for (int j = T.size() - 1; j >= 0; --j) {
                f[j + 1] += S[i] == T[j] ? f[j] : 0;
            }
        }

        return f[T.size()];
    }
};

Java代码:

public class Solution {
    static int dp[][];
    static int numDistinctRecr(char s[],char t[],int i,int j){
        if(s.length - i < t.length - j) return 0;
        if(j == t.length) return 1;
        if( i >= s.length || j>= t.length ) return 0;
        if(dp[i][j] >= 0) return dp[i][j];
        if(s[i] == t[j]){ //当前这个字符相等
            return (dp[i][j] = numDistinctRecr(s, t, i+1, j) + numDistinctRecr(s,t,i+1,j+1));
        }else{//不同的只能删掉
            return (dp[i][j] = numDistinctRecr(s, t, i+1,j ));
        }
    }

    public static int numDistinct(String S, String T) {
        dp = new int[S.length()][T.length()];
        for(int i=0; i<S.length(); i++)
            for(int j=0; j<T.length(); j++)
                dp[i][j] = -1;
        return numDistinctRecr(S.toCharArray(), T.toCharArray(), 0, 0);
    }
}

  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }

  3. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?