千问 LeetCode 2478.完美分割的方案数 public int beautifulPartitions(String s, int k, int minLength)

好的，这是 LeetCode 2478 "完美分割的方案数" 的 Java 实现。解题思路核心是动态规划 + 前缀和优化：1. 定义状态：dp[i][j] 表示前 i 个字符分成 j 段的方案数2. 状态转移：对于每个可能的分割点，需要满足： - 当前段长度 ≥ minLength - 当前段首字符是质数（2,3,5,7） - 当前段尾字符是非质数3. 优化：使用前缀和避免 O(n²k) 的复杂度，降到 O(nk)Java 实现class Solution { public int beautifulPartitions(String s, int k, int minLength) { final int MOD = 1_000_000_007; int n = s.length(); // 快速判断质数 boolean[] isPrime = new boolean[10]; isPrime[2] = isPrime[3] = isPrime[5] = isPrime[7] = true; // 第一个字符必须是质数，最后一个字符必须是非质数 if (!isPrime[s.charAt(0) - '0'] || isPrime[s.charAt(n-1) - '0']) { return 0; } // dp[i][j] 表示前 i 个字符分成 j 段的方案数 int[][] dp = new int[n + 1][k + 1]; dp[0][0] = 1; // 前缀和数组，pre[i][j] = sum(dp[0][j] + dp[1][j] + ... + dp[i][j]) int[][] pre = new int[n + 1][k + 1]; pre[0][0] = 1; for (int i = 1; i = n; i++) { // 判断第 i 个字符能否成为一段的结尾 //