题目描述
leetcode 困难题
给你一个字符串 s ，每个字符是数字 ‘1’ 到 ‘9’ ，再给你两个整数 k 和 minLength 。
如果对 s 的分割满足以下条件，那么我们认为它是一个 完美 分割：
- s 被分成 k 段互不相交的子字符串。
- 每个子字符串长度都 至少 为 minLength 。
- 每个子字符串的第一个字符都是一个 质数 数字，最后一个字符都是一个 非质数 数字。质数数字为 ‘2’ ，’3’ ，’5’ 和 ‘7’ ，剩下的都是非质数数字。
请你返回 s 的 完美 分割数目。由于答案可能很大，请返回答案对 109 + 7 取余 后的结果。
一个 子字符串 是字符串中一段连续字符串序列。
示例1：
1
2
3
4
5
6
| 输入：s = "23542185131", k = 3, minLength = 2
输出：3
解释：存在 3 种完美分割方案：
"2354 | 218 | 5131"
"2354 | 21851 | 31"
"2354218 | 51 | 31"
|
提示1：
1
2
| 1 <= k, minLength <= s.length <= 1000
s 每个字符都为数字 '1' 到 '9' 之一。
|
动态规划
定义 $f(i, j)$ 表示字符串 $S[0..(j -1)]$ 分割 $i$ 份时的满足题目要求的方案数。
所以 $j$ 如果为一个合法的分割点，需满足 $j$ 为非质数，且 $j - 0 >= minLength - 1$。
而对于 $f(i, j)$ 的求解，我们通过可以枚举上一个分割点来得出，定义其为 $j’$，需满足 $j’$ 为非质数，$j’ + 1$ 为质数，$j - j’ >= minLength$。
那么就可以得到 $f(i, j)$ 为所有符合要求的 $f(i - 1, j’)$ 的总和。
定义 $f(0,0)$ 为 $1$ ，即空串的 $0$ 个分割算作一种方案，$f(k, n)$ 为答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
private static final Set<Character> P = Set.of('2', '3', '5', '7');
private static final int MOD = (int)(1e9 + 7);
public int beautifulPartitions(String s, int k, int minLength) {
int n = s.length();
int[][] dp = new int[k + 1][n + 1];
dp[0][0] = 1;
for(int i = 1; i < k + 1; i++){
for(int j = minLength - 1; j < n; j++){
if(isP(s.charAt(j))){
continue;
}
int sum = 0;
for(int q = -1; q <= j - minLength; q++){
if((q == - 1 || !isP(s.charAt(q))) && isP(s.charAt(q + 1))){
sum = (sum + dp[i - 1][q + 1]) % MOD;
}
}
dp[i][j + 1] = sum;
}
}
return dp[k][n];
}
private boolean isP(char c){
return P.contains(c);
}
}
|
会发现上面代码的时间复杂度为 $O(N^3)$，会 TLE ，需要进行优化。
可以发现对于同一个 $i$ 的不同 $j$ ，许多 $j’$ 的枚举是重复的。
所以可以同时进行 $j$ 和 $j’$ 的枚举，并且利用类似前缀和的思路，记录对于同一个 $i$ 不同 $j’$ 的总和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
private static final Set<Character> P = Set.of('2', '3', '5', '7');
private static final int MOD = (int)(1e9 + 7);
public int beautifulPartitions(String s, int k, int minLength) {
int n = s.length();
int[][] dp = new int[k + 1][n + 1];
dp[0][0] = 1;
for(int i = 1; i < k + 1; i++){
int sum = 0;
for(int j = minLength - 1; j < n; j++){
int q = j - minLength;
if((q == - 1 || !isP(s.charAt(q))) && isP(s.charAt(q + 1))){
sum = (sum + dp[i - 1][q + 1]) % MOD;
}
if(isP(s.charAt(j))){
continue;
}
dp[i][j + 1] = sum;
}
}
return dp[k][n];
}
private boolean isP(char c){
return P.contains(c);
}
}
|