力扣2478题：动态规划与前缀和解决质数分段问题
一、题目解读
力扣2478题要求将字符串s划分为k个连续子串，每个子串的首字符均为质数，且长度≥minLength。题目需计算满足条件的不同划分方案数（对1e9+7取模）。核心在于质数判断与子串划分的组合优化，需兼顾效率与准确性。
二、解题思路
1. 预处理质数判断：使用lambda函数快速判定字符是否为质数（仅考虑'2', '3', '5', '7'）。
2. 边界条件校验：若首字符非质数或尾字符是质数，直接判定无解。
3. 动态规划核心：
○ 定义dp[i][j]：前i个字符划分为j段的方案数。
○ 状态转移方程：若子串s[i−minLength+1…i]首尾为质数，则dp[i][j] += dp[i−minLength][j−1]。
4. 前缀和优化：避免重复计算中间状态，通过滚动数组减少空间复杂度。
三、解题步骤
1. 初始化：dp[0][0]=1（空串视为一种合法划分）。
2. 外层循环j（段数）：
计算前缀和prefix，记录dp[i][j−1]的累积值。
内层循环i（字符位置）：
若i<minLength跳过（不满足长度限制）。
检查s[i]是否为首尾质数子串末尾：是，则将prefix[i−minLength]加入dp[i][j]（对应新增一段）。
取模防止溢出。
3. 最终结果：dp[n][k]即为所求方案数。
四、代码与注释
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];
}
};注：代码通过分段合法性的严格判定与前缀和加速，实现O(nk)时间与O(nk)空间复杂度（可优化空间至O(k)）。
五、总结
本题通过动态规划将复杂划分问题拆解为子问题，结合质数特性与前缀和优化，大幅降低计算冗余。关键在于：
1. 质数预处理提升判断效率；
2. 严格校验首尾字符边界条件；
3. 滚动前缀和避免空间爆炸。
该解法适用于需要组合优化与状态压缩的算法题目，对算法设计与面试场景具有实用价值。
原创内容 转载请注明出处
