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

fiwhgikbl

一、问题分析

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

• 分成k段互不相交的子串
• 每个子串长度至少为minLength
• 每个子串首字符是质数(2,3,5,7)，尾字符是非质数(1,4,6,8,9)
  
  

二、解题思路

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

• 预处理质数判断数组
• 定义dp[j]表示前i个字符分成j段的**分割数目
• 通过双重循环填充dp表
• 最终结果为dp[n][k]
  
  

三、C++代码实现

1. class Solution {
   
2. public:
   
3. int beautifulPartitions(string s, int k, int minLength) {
   
4. const int MOD = 1e9 + 7;
   
5. int n = s.size();
   
6. 
   
7. // 预处理质数判断
   
8. auto isPrime = [](char c) {
   
9. return c == '2' || c == '3' || c == '5' || c == '7';
   
10. };
    
11. 
    
12. // 检查首尾字符是否满足条件
    
13. if (!isPrime(s[0]) || isPrime(s.bACk())) return 0;
    
14. 
    
15. // dp[i][j]表示前i个字符分成j段的方案数
    
16. vector<vector<int>> dp(n + 1, vector<int>(k + 1, 0));
    
17. dp[0][0] = 1;
    
18. 
    
19. for (int j = 1; j <= k; ++j) {
    
20. // 前缀和优化，避免重复计算
    
21. vector<int> prefix(n + 1, 0);
    
22. prefix[0] = dp[0][j - 1];
    
23. 
    
24. for (int i = 1; i <= n; ++i) {
    
25. prefix[i] = (prefix[i - 1] + dp[i][j - 1]) % MOD;
    
26. }
    
27. 
    
28. for (int i = 1; i <= n; ++i) {
    
29. if (i < minLength) continue;
    
30. if (!isPrime(s[i - 1]) && (i == n || isPrime(s[i]))) {
    
31. int start = max(0, i - minLength);
    
32. dp[i][j] = (dp[i][j] + prefix[start]) % MOD;
    
33. }
    
34. }
    
35. }
    
36. 
    
37. return dp[n][k];
    
38. }
    
39. };

复制代码

四、代码详解

• ‌预处理阶段‌：

  
  
  • 定义isPrime函数判断字符是否为质数
  • 检查首尾字符是否满足条件（首字符质数，尾字符非质数）
    
    

• ‌动态规划表初始化‌：

  
  
  • dp[0][0] = 1表示空字符串分成0段的方案数为1
  • 使用二维数组dp[j]记录状态
    
    

• ‌填充dp表‌：

  
  
  • 外层循环遍历分割段数j
  • 使用前缀和数组优化计算
  • 内层循环遍历字符串长度i
  • 检查分割点是否满足条件
    
    

• ‌结果返回‌：

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

五、算法优化

• ‌前缀和优化‌：

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

• ‌提前终止条件‌：

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

六、、扩展思考

• 如果minLength不是固定值而是每个子串有不同的最小长度要求，如何修改算法？
• 如果条件改为首尾字符都必须是质数，算法需要做哪些调整？
• 如何优化空间复杂度，使其仅使用O(n)的额外空间？
  
  

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

来源：力扣2478题解：动态规划解决字符串**分割问题

admin