题目分析

本题是第320场周赛的第四题，从题目的意思和数据范围可以看出需要使用动态规划求解，dp的描述也比较清晰，使用dp[i][j]表示前j个字符分成i段的方案数。提示到这里，小伙伴尝试自己写一下。

动态规划

状态转移方程如下：

$$ dp[i][j] = dp[i - 1][minIdx - minLength] + dp[i - 1][minIdx - minLength + 1] + … + dp[i - 1][j - minLength] $$

$$ minIdx = i \times minLength $$

$$ maxIdx = n - (k - i) \times minLength $$

$$ minIdx \le j \le maxIdx $$

因此可以推算出来上述算法的时间复杂度是$O(kn^2)$，在本题的数据范围内会超时，能否再进行优化呢？

我们发现计算dp[i][j]时要计算dp[i - 1][i x minLength]到dp[i - 1][j - minLength]，而计算dp[i][j + 1]时，要计算dp[i - 1][i x minLength]到dp[i - 1][j + 1 - minLength]，除了最后一个元素外，全都是重复的。

因此可以在遍历j的时候，用sum记录从dp[i - 1][i x minLength]到dp[j - minLength]的和。当遍历j + 1的时候，只需要用sum + dp[i - 1][j + 1- minLength]即可得到新的sum。

这里要注意，只有符合条件的分割方式才能被加入到sum中，也只有符合条件的分割方式才能记录到dp[i][j]中。

因此使用上述优化可以省去一维时间复杂度。算法的时间复杂度为O(kn)，空间复杂度为O(kn)。

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    private static final HashSet<Character> PRIME = new HashSet<>() {
        {
            add('2');
            add('3');
            add('5');
            add('7');
        }
    };

    private String s;

    private int n;

    public int beautifulPartitions(String s, int k, int minLength) {
        n = s.length();
        this.s = s;
        if (n < k * minLength || !PRIME.contains(s.charAt(0)) || PRIME.contains(s.charAt(n - 1))) {
            return 0;
        }
        int[][] dp = new int[k + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            int sum = 0;
            for (int j = i * minLength; j <= n - (k - i) * minLength; j++) {
                if (isOk(j - minLength)) {
                    sum = (sum + dp[i - 1][j - minLength]) % MOD;
                }
                if (isOk(j)) {
                    dp[i][j] = sum;
                }
            }
        }
        return dp[k][n];
    }

    private boolean isOk(int j) {
        return j == 0 || j == n || !PRIME.contains(s.charAt(j - 1)) && PRIME.contains(s.charAt(j));
    }
}

刷题总结

这个题目思路容易想，但是能优化到二维是不容易的，希望小伙伴多多练习，一定要把动态规划拿下。