2478.完美分割的方案数

链接：2478.完美分割的方案数
难度：Hard
标签：字符串、动态规划
简介：给你一个字符串 s ，每个字符是数字 '1' 到 '9' ，再给你两个整数 k 和 minLength 。请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 109 + 7 取余 后的结果。

题解 1 - cpp

• 编辑时间：2022-11-20
• 执行用时：32ms
• 内存消耗：30.4MB
• 编程语言：cpp
• 解法介绍：dp[i][j]表示总共分成 i 组总共字符有 j 个的合理方案数。

class Solution {
public:
    string s;
    int n;
    const int mod = 1e9 + 7;
    bool isPrime(int i) {
        return s[i] == '2' || s[i] == '3' || s[i] == '5' || s[i] == '7';
    }
    bool canPart(int i) {
        return i == 0 || i == n || !isPrime(i - 1) && isPrime(i);
    }
    int beautifulPartitions(string s, int k, int minLength) {
        this->s = s;
        n = s.size();
        if (!isPrime(0) || isPrime(n - 1) || k * minLength > n) return false;
        vector<vector<int>> dp(k + 1, vector<int>(n + 1, 0));
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            int sum = 0;
            for (int j = i * minLength; j + (k - i) * minLength <= n; j++) {
                if (canPart(j - minLength)) sum = (sum + dp[i - 1][j - minLength]) % mod;
                if (canPart(j)) dp[i][j] = sum;
            }
        }
        return dp[k][n];
    }
};