面试算法97：子序列的数目

题目

输入字符串S和T，请计算字符串S中有多少个子序列等于字符串T。例如，在字符串"appplep"中，有3个子序列等于字符串"apple"

分析

为了解决这个问题，每步从字符串S中取出一个字符判断它是否和字符串T中的某个字符匹配。字符串S中的字符可能和字符串T中的多个字符匹配，如字符串T中的字符’p’可能和字符串S中的3个’p’匹配，因此每一步可能面临多个选择。解决一个问题需要多个步骤，并且每步都可能面临多个选择，这看起来很适合运用回溯法。但由于这个问题没有要求列出字符串S中所有等于字符串T的子序列，而是只计算字符串S中等于字符串T的子序列的数目，也就是求解数目，因此，这个问题更适合运用动态规划来解决。
用f(i，j)表示字符串S[0…i]中等于字符串T[0…j]的子序列的数目。如果字符串S的长度是m，字符串T的长度是n，那么f(m-1，n-1)就是字符串S中等于字符串T的子序列的数目

解

public class Test {
    public static void main(String[] args) {
        int result = numDistinct("appplep", "apple");
        System.out.println(result);

    }

    // 用f(i，j)表示字符串S[0..i]中等于字符串T[0..j]的子序列的数目
    // 如果字符串S的长度是m，字符串T的长度是n，那么f(m-1，n-1)就是字符串S中等于字符串T的子序列的数目
    public static int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        dp[0][0] = 1;

        for (int i = 0; i < s.length(); i++) {
            dp[i + 1][0] = 1;
            for (int j = 0; j <= i && j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    // 两个值相等，则有两个选择：
                    //    dp[i][j]:代表用S[i]去匹配T[j]，则f(i，j) = f(i-1，j-1)
                    //    dp[i][j+1]:代表是舍去S[i]，则f(i，j) = f(i-1，j)
                    //    dp[i+1][j+1]:代表着两种选择的总和
                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                }
                else {
                    // 两个值不相等，则只有一种选择:舍去S[i]
                    dp[i + 1][j + 1] = dp[i][j + 1];
                }
            }
        }

        return dp[s.length()][t.length()];
    }
}