leetcode-distinct-subsequences

题目大意

　　https://leetcode.com/problems/distinct-subsequences/

　　给你字符串s和t，计算s中有多少个子序列与t相等

题目分析

　　比较基础的动态规划，最开始我用记忆化搜索，导致递归层数太多，栈溢出。只能用递推方程了，方程不难，直接看代码理解一下。

代码

public class Solution {
    
    public int numDistinct(String s, String t) {
        int len1 = s.length();
        int len2 = t.length();
        if (len1 == 0 || len1 < len2) {
            return 0;
        }
        if (len2 == 0) {
            return 1;
        }
        char[] c1 = s.toCharArray();
        char[] c2 = t.toCharArray();
        int[][] f = new int[len1 + 1][len2 + 1];
        f[len1 - 1][len2 - 1] = ((c1[len1 - 1] == c2[len2 - 1]) ? 1 : 0);
        for (int i = len1 - 2; i >= 0; i--) { // 边界情况预处理一下
            f[i][len2 - 1] = f[i + 1][len2 - 1];
            f[i][len2 - 1] += ((c1[i] == c2[len2 - 1]) ? 1 : 0);
        }
        for (int i = len1 - 2; i >= 0; i--) {
            for (int j = len2 - 2; j >= 0; j--) {
                if (c1[i] == c2[j]) { // 相等，则有两种情况都要加
                    f[i][j] += (f[i + 1][j] + f[i + 1][j + 1]);
                } else {
                    f[i][j] += f[i + 1][j];
                }
            }
        }
        return f[0][0];
    }
}