力扣2478题解：动态规划解决字符串完美分割问题

一、问题分析

这道题目要求我们计算将数字字符串分割成k个子串的"完美分割"方式数目。完美分割需要满足三个条件：

1. 分成k段互不相交的子串

2. 每个子串长度至少为minLength

3. 每个子串首字符是质数(2,3,5,7)，尾字符是非质数(1,4,6,8,9)

二、解题思路

我们可以使用动态规划来解决这个问题：

1. 预处理质数判断数组

2. 定义dp[i][j]表示前i个字符分成j段的完美分割数目

3. 通过双重循环填充dp表

4. 最终结果为dp[n][k]

三、C++代码实现

class Solution {
public:
    int beautifulPartitions(string s, int k, int minLength) {
        const int MOD = 1e9 + 7;
        int n = s.size();
        
        // 预处理质数判断
        auto isPrime = [](char c) {
            return c == '2' || c == '3' || c == '5' || c == '7';
        };
        
        // 检查首尾字符是否满足条件
        if (!isPrime(s[0]) || isPrime(s.bACk())) return 0;
        
        // dp[i][j]表示前i个字符分成j段的方案数
        vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
        dp[0][0] = 1;
        
        for (int j = 1; j <= k; ++j) {
            // 前缀和优化，避免重复计算
            vector<int> prefix(n + 1, 0);
            prefix[0] = dp[0][j - 1];
            
            for (int i = 1; i <= n; ++i) {
                prefix[i] = (prefix[i - 1] + dp[i][j - 1]) % MOD;
            }
            
            for (int i = 1; i <= n; ++i) {
                if (i < minLength) continue;
                if (!isPrime(s[i - 1]) && (i == n || isPrime(s[i]))) {
                    int start = max(0, i - minLength);
                    dp[i][j] = (dp[i][j] + prefix[start]) % MOD;
                }
            }
        }
        
        return dp[n][k];
    }
};

四、代码详解

1. ‌预处理阶段‌：

• 定义isPrime函数判断字符是否为质数

• 检查首尾字符是否满足条件（首字符质数，尾字符非质数）

2. ‌动态规划表初始化‌：

• dp[0][0] = 1表示空字符串分成0段的方案数为1

• 使用二维数组dp[i][j]记录状态

3. ‌填充dp表‌：

• 外层循环遍历分割段数j

• 使用前缀和数组优化计算

• 内层循环遍历字符串长度i

• 检查分割点是否满足条件

4. ‌结果返回‌：

• 最终结果为dp[n][k]对1e9+7取模

五、算法优化

1. ‌前缀和优化‌：

• 使用prefix数组避免重复计算，将时间复杂度从O(n^2k)优化到O(nk)

2. ‌提前终止条件‌：

• 如果首字符不是质数或尾字符是质数，直接返回0

六、、扩展思考

1. 如果minLength不是固定值而是每个子串有不同的最小长度要求，如何修改算法？

2. 如果条件改为首尾字符都必须是质数，算法需要做哪些调整？

3. 如何优化空间复杂度，使其仅使用O(n)的额外空间？

掌握这种动态规划解法，能够帮助你解决许多类似的字符串分割和组合问题！