题解 | #不同的子序列#

无空间优化版本:

    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return int整型
         返回 S 的子序列中 == T 的不同子序列的个数!
         即返回 能够把 S 转换为  T 的所有办法! 
       // f(i,j) 代表 S[0,i-1] 中 ==  T[0,j-1] 的子串个数!
       // 状态转移 f(i,j) = S[i-1] == T[j-1] ? f(i-1,j-1) + f(i-1,j) : f(i-1,j); 
     */
    public int numDistinct (String S, String T) {
       if(T.length() > S.length()) return 0;
       
        int m = S.length();
        int n = T.length();
        
        int[][] dp = new int[m+1][n+1]; 
        // 空串的子串和空串匹配存在唯一一个!
        dp[0][0] = 1;
        
        // 当 T 为空串时,只存无论 S多长,都只有一个子串空串!
        for(int i = 1; i <= m ; i++){
            dp[i][0] = 1;
        }
        
        // 当 T .length > S.length S中不可能存在子串 == T
        for(int i = 1; i <= n; i++){
            dp[0][i] = 0;
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
              
                if(S.charAt(i-1) == T.charAt(j-1)){
                       // S的第i个字符与T的第j个字符相同
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
                }else {
                      // S的第i个字符与T的第j个字符不相同
                     // 从S的前i-1个字符中找子串，使子串与T的前j个字符相同
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[m][n];
    }

空间优化版本 :

    public int numDistinct (String S, String T) {
       if(T.length() > S.length()) return 0;
        int m = S.length();
        int n = T.length();
        
        int[] dp = new int[n+1]; 
        // 空串的子串和空串匹配存在唯一一个!
        dp[0] = 1;
        
        // 当 T .length > S.length S中不可能存在子串 == T
        for(int i = 1; i <= n; i++){
            dp[i] = 0;
        }
        /*
            一维数组的话,求当前位置的值 依赖于数组上一次结果的当前位置 于 当前位置的前一个位置所以采用 反向迭代!
        */
        for(int i = 1; i <= m; i++){
            for(int j = n; j > 0; j--){
                  if(S.charAt(i-1) == T.charAt(j-1))
                  dp[j] = dp[j-1] + dp[j];
            }
        }
        return dp[n];
    }