动态规划-计数dp-Distinct Subsequences II

2020-02-06 17:01:36

问题描述：

问题求解：

非常经典的计数dp问题，思路就是统计以每个字符为结尾的个数，最后求和即可。

dp[i] = sum of (dp[j]) 0 <= j <= i；可以理解为将最后的一个字符追加到前面的字符串后面。

问题是如何去重。

当我们遇到相同的字符的时候，首先最后一个字符单独最为subseq要删除，因为前面计算过了，其次，只能加到第一次碰到形同字符的位置，因为再前面的在这个重复字符的位置已经计算过了。

    int mod = (int)1e9 + 7;

    public int distinctSubseqII(String S) {

        int n = S.length();

        int[] dp = new int[n];

        Arrays.fill(dp, 1);

        for (int i = 0; i < n; i++) {

            for (int j = i - 1; j >= 0; j--) {

                if (S.charAt(i) != S.charAt(j)) dp[i] = (dp[i] % mod + dp[j] % mod) % mod;

                else {

                    dp[i] -= 1;

                    dp[i] = (dp[i] % mod + dp[j] % mod) % mod;

                    break;

                }

            }

        }

        int res = 0;

        for (int i = 0; i < n; i++) res = (res % mod + dp[i] % mod) % mod;

        return res;

    }

巴特西

动态规划-计数dp-Distinct Subsequences II

最新文章

热门文章