不同的子序列

class Solution {
public:
int numDistinct(string S, string T) {
    int len=T.size();
    vector<int> array(len+1);
    array[0]=1;
    for(int i=1;i<S.size()+1;i++){
        for(int j=min(i,len);j>0;j--){
            if(S[i-1]==T[j-1])
                array[j]=array[j]+array[j-1];
        }
    }
    return array[len];
    }
};

这种dp题目，不看答案一个字都写不出来，看完答案觉得一点都不难。。。

原理不多说，上面的大神已经说得很清楚了，下面晒出我的示意图和代码：

public int numDistinct(String S, String T) {
        if (S == null || T == null || T.length() == 0 || S.length() < T.length()) {
            return 0;
        }
        int sLen = S.length();
        int tLen = T.length();
        int[][] array = new int[sLen + 1][tLen + 1];
        // 初始化第一行，字符串S为""，除了子字符串为""的情况，结果全部为0
        for (int i = 1; i < tLen + 1; i++) {
            array[0][i] = 0;
        }
        // 初始化第一列，子字符串为"",结果全部为1
        for (int i = 0; i < sLen + 1; i++) {
            array[i][0] = 1;
        }
        for (int i = 1; i < sLen + 1; i++) {
            // j>i时子序列的长度大于源数列，结果为0，无需遍历
            // 或者for (int j = 1; j <= Math.min(i, tLen); j++)
            for (int j = Math.min(i, tLen); j > 0; j--) {
                // 如果当前位置的字母不同
                if (S.charAt(i - 1) != T.charAt(j - 1)) {
                    array[i][j] = array[i - 1][j];
                } else {// 如果当前位置的字母相同
                    array[i][j] = array[i - 1][j] + array[i - 1][j - 1];
                }
            }

        }
        return array[sLen][tLen];
    }

    // 因为当前结果只取决于上一行结果的当前位置和后面一位，因此可以降维
    public int numDistinct2(String S, String T) {
        if (S == null || T == null || T.length() == 0 || S.length() < T.length()) {
            return 0;
        }
        int sLen = S.length();
        int tLen = T.length();
        int[] array = new int[tLen + 1];
        array[0] = 1;
        for (int i = 1; i < sLen + 1; i++) {
            for (int j = Math.min(i, tLen); j > 0; j--) {
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    array[j] = array[j] + array[j - 1];
                }
            }
        }
        return array[tLen];
    }

/*
 *	思路：dp题。
 *	状态定义：dp[i][j]代表s[0~i-1]中T[0~j-1]不同子串的个数。
 *	递推关系式：S[i-1]!= T[j-1]：	DP[i][j] = DP[i][j-1] （不选择S中的s[i-1]字符）
 *				S[i-1]==T[j-1]：	DP[i][j] = DP[i-1][j-1]（选择S中的s[i-1]字符） + DP[i][j-1]
 *  初始状态：第0列：DP[i][0] = 0，第0行：DP[0][j] = 1
 */

public class Solution {
    public int numDistinct(String S, String T) {
        int row = S.length() + 1;
        int col = T.length() + 1;
        int[][] dp = new int[row][col];
        for (int i = 1; i < col; i++) {
        	dp[0][i] = 0;
        }
        for (int i = 0; i < row; i++) {
        	dp[i][0] = 1;
        }
        for (int i = 1; i < row; i++) {
        	for (int j = 1; j < col; 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[row - 1][col - 1];
    }
}

class Solution {
public:
    int numDistinct(string S, string T) {
        map<int,int> dp;
        for(int j=0;j<S.size();j++)
            for(int i=T.size()-1;i>=0;i--)
            if(T[i]==S[j]){
               if(i!=0) dp[i]+=dp[i-1];
               else dp[0]++;
            }
        return dp[T.size()-1];
    }
};

class Solution:
    def numDistinct(self , S , T ):
        # write code here
        m = len(S)
        n = len(T)
        if m < n:
            return(0)
        elif m * n == 0 or S == T:
            return(1)
        else:
            res = [[0 for i in range(m)] for j in range(n)]
            for j in range(m):
                if S[j] == T[0]:
                    for x in range(j,m):
                        res[0][x] += 1
            for i in range(1,n):
                for j in range(1,m):
                    if S[j] == T[i]:
                            res[i][j] = res[i-1][j-1]+res[i][j-1]
                    else:
                        res[i][j] = res[i][j-1]
            return(res[n-1][m-1])

class Solution {
    /**
     *  DP: 假设dp[i][j]是S中前i个字符构成的子串和T中前j个字符构成
     *  的子串匹配得到的子序列数量，求dp[S.length()][T.length()]
     *  1. 初始条件dp[i][0],S的前i的任意子串与空串有一个匹配的序列,dp[i][0]=1
     *     初始条件dp[0][j](j>0),S的空串与任意非空串无匹配的子序列,dp[0][j]=0
     *  2. 转义条件，求dp[i][j]的值有两种情况：
     *      1）S[i-1]!=T[j-1], dp[i][j]=dp[i-1][j] S的i-1位置与T的j-1不匹配
     *          那么符合的匹配序列数量和S的前i-1个字符的子串一样
     *      2) S[i]==T[j-1], dp[i][j]=dp[i-1][j]+dp[i-1][j-1] S的i-1与T的j-1匹配
     *          那么符合匹配的序列数等于前i-1就符合与T前j匹配的,加上S前i-1子串和
     *          T的前j-1子串匹配的。
     */
    public int numDistinct(String s, String t) {
        int[][] num = new int[s.length()+1][t.length()+1];
        for(int i=0; i<=s.length(); i++){
            num[i][0] = 1;
        }
        for(int i=1; i<=s.length(); i++){
            for(int j=1; j<=t.length(); j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    num[i][j] = num[i-1][j] + num[i-1][j-1];
                } else {
                    num[i][j] = num[i-1][j];
                }
            }
        }
        return num[s.length()][t.length()];
    }
}

class Solution {
public:
    int numDistinct(string S, string T) {
        S=" "+S,T=" "+T;
        int n=S.length(),m=T.length(),i,j;
        vector<vector<int> > dp(n+1,vector<int>(m+1,0));
        for(i=0;i<=n;i++) dp[i][0]=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++){
                dp[i][j]=dp[i-1][j];
                if(S[i]==T[j])
                    dp[i][j]+=dp[i-1][j-1];
            }
        return dp[n][m];
    }
};

public class Solution {  
        public int numDistinct(String S, String T) {  
            if (S == null || T == null) return 0;  
            if (S.equals("") || T.equals("")) return 0;  
              
            //table[i][j]表示S[0~i]中有多少个T[0~j]的个数  
            int[][] table = new int[S.length()][T.length()];  
              
            //给table第一行赋值，意思是S[0]中有多少个T[0~j]  
            //显然，S[0]最多包含一个T[0]，故table[0][1~n]都为0  
            if (S.charAt(0) == T.charAt(0)) {  
                table[0][0] = 1;  
            }  
              
            for (int i = 1; i < S.length(); i++) {  
                char s = S.charAt(i);  
                  
                //给table[i][0]赋值，意思是S[0~i]中有多少个T[0]  
                if (s == T.charAt(0)) {  
                    table[i][0] = table[i - 1][0] + 1;  
                } else {  
                    table[i][0] = table[i - 1][0];  
                }  
                  
                for (int j = 1; j < T.length(); j++) {  
                    char t = T.charAt(j);  
                    if (s == t) {  
                        //如果用S[i]匹配T[j]，那么S[0~i-1]敏感词有table[i-1][j-1]个T[0~j-1]  
                        //如果不用S[i]匹配T[i]，那么S[0~i]敏感词有table[i-1][j]个T[0~j]  
                        table[i][j] = table[i - 1][j - 1] + table[i - 1][j];  
                    } else {  
                        //S[i]!=T[j]时，S[0~i]敏感词有table[i-1][j]个T[0~j]  
                        table[i][j] = table[i - 1][j];  
                    }  
                }  
                  
            }  
              
            return table[S.length() - 1][T.length() - 1];  
        }  
    }

public int numDistinct(String s, String t) {
		if(s==null||t==null)
			return 0;
		int[][] res=new int[t.length()+1][s.length()+1];
		for(int i=0;i<=s.length();i++){
			res[0][i]=1;
		}
		for(int i=0;i<t.length();i++){
			for(int j=0;j<s.length();j++){
				if(t.charAt(i)==s.charAt(j))
					res[i+1][j+1]=res[i][j]+res[i+1][j];
				else
					res[i+1][j+1]=res[i+1][j];
				
			}
		}
		
		return res[t.length()][s.length()];
	}

// 关键在于弄清楚对退公式与状态矩阵
// dp[i][j] 表示 S中的前i个字符构成的字符串包含 T 中前j个字符构成的字符串的 子串的个数
// 当S【i-1】 == t【j-1】时， 则新的dp值可以是 不使用第i个字符，却能构成T中j子串的个数dp[i][j] 加上
// 不使用第i个字符能构成T中j-1子串的个数dp[i-1][j-1]
// 否则，只能是等于dp[i-1][j]
class Solution {
public:
    int numDistinct(string S, string T) {
        int slen = S.length();
        int tlen = T.length();
        
        vector<vector<int>> dp;
        vector<int> temp(tlen+1,0);
        temp[0] = 1;
        
        for( int i = 0; i <= slen; i++)
            dp.push_back( temp );
        
        for( int i = 1; i <= slen ; i++)
            for(int j = 1 ; j <= tlen ; j++)
            {
            	if( S[i-1] == T[j-1] )
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
            	else
                    dp[i][j] = dp[i-1][j];
        	}
         return dp[slen][tlen];
    }
};

class Solution {
public:
    int numDistinct(string S, string T) {
        int l = T.length();
        vector<int> result(l+1);
        result[0] = 1;
        for(int i=1;i<=S.length();i++)
        	for(int j=min(i,l);j>0;j--)
        	{
        		if(S[i-1] == T[j-1])
        			result[j] = result[j] + result[j-1];
			}
        return result[l];
    }
};

我们需要一个二维数组dp(i)(j)来记录长度为i的字串在长度为j的母串中出现的次数，这里长度都是从头算起的，而且遍历时，保持子串长度相同，先递增母串长度，母串最长时再增加一点子串长度重头开始计算母串。

首先我们先要初始化矩阵，当子串长度为0时，所有次数都是1，当母串长度为0时，所有次数都是0.当母串子串都是0长度时，次数是1（因为都是空，相等）。接着，如果子串的最后一个字母和母串的最后一个字母不同，说明新加的母串字母没有产生新的可能性，可以沿用该子串在较短母串的出现次数，所以dp(i)(j) = dp(i)(j-1)。如果子串的最后一个字母和母串的最后一个字母相同，说明新加的母串字母带来了新的可能性，我们不仅算上dp(i)(j-1)，也要算上新的可能性。那么如何计算新的可能性呢，其实就是在既没有最后这个母串字母也没有最后这个子串字母时，子串出现的次数，我们相当于为所有这些可能性都添加一个新的可能。所以，这时dp(i)(j) = dp(i)(j-1) + dp(i-1)(j-1)。下图是以rabbbit和rabbit为例的矩阵示意图。计算元素值时，当末尾字母一样，实际上是左方数字加左上方数字，当不一样时，就是左方的数字。

示意图

class Solution {
public:
    int numDistinct(string S, string T) {
        // write code here
        int lens = S.length();
        int lent = T.length();
        vector<vector<int>> dp(lens+1,vector<int>(lent+1));
        //第一行设置为0 第一列设置为1
        dp[0][0] = 1;
        for(int i=1;i<=lens;++i)
        {
            dp[i][0]=1;
            for(int j=1;j<=lent;++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[lens][lent];
    }
};