LeetCode 115.不同的子序列

LeetCode 115.不同的子序列

双序列型动态规划
确定状态:
类似于LCS的思路,以最后一步的T为出发点。

  • 情况1:T[n-1]=A[m-1],则求T[0..n-2]S[0..m-2]中出现多少次
  • 情况2:T[n-1]!=S[m-1],则不考虑S[m-1],求T[0..n-1]S[0..m-2]中出现多少次
    -状态:设f[i][j]T前j个字符T[0..j-1]S前i个字符S[0..i-1]中出现多少次
    两种情况相加即可。(加法原理)
    转移方程:
    f[i][j]=f[i-1][j-1](T[i-1]==S[j-1]+f[i-1][j])
    初始条件:
    如果T是空串,TS中出现次数是1:f[i][0]=1
    如果S是空串,而T不是空串,出现次数是0:f[0][j]=0
class Solution {
    public int numDistinct(String s, String t) {
        char[] s1=s.toCharArray();
        char[] s2=t.toCharArray();
        int m=s1.length;
        int n=s2.length;
        int[][] f=new int[m+1][n+1];
        int i,j;
        for(i=0;i<=m;i++){
            f[i][0]=1;
        }
        for(i=1;i<=n;i++){
            f[0][i]=0;
        }
        for(i=1;i<=m;i++){
            for(j=1;j<=n;j++){
                f[i][j]=f[i-1][j];
                if(s1[i-1]==s2[j-1]){
                    f[i][j]+=f[i-1][j-1];
                }
            }
        }
        return f[m][n];
    }
}