leetcode：2478. 完美分割的方案数【预处理 + dp定义 + 前缀和优化】

题目截图

题目分析

• 开头必定是prime，结尾必定是not prime
• k = 1特判
• 找到所有可能的结尾点（最后一个不考虑）
• 结尾点i必须满足s[i]->not prime, s[i + 1]->prime
• 设结尾点集合为x
• 0 <= x1 < x2 < … < xm <= n - 1 选k - 1个点
• 不妨设为b1, b2, … b(k - 1), 满足
• 1.b1 + 1 >= minLength
• 2.bi - b(i - 1) >= minLength, i belongs to [1, k - 1]
• 3.n - 1 - b(k - 1) >= minLength
• 那么，这大概可以考虑dp
• 变量有前i个结束点，第j个实际结束段，minLength为定值不考虑
• 那么，dp[i][j]表示第i个结束点作为第j个结束段点的个数
• 答案为所有满足i作为n - 1 - x[i] >= minLength，的dp[i][-1]之和
• 转移方程：对于dp[i][j]而言，找到所有的i2使得x[i] - x[i2] >= minLength，那么dp[i][j] = sum(dp[i2][j - 1])
• i2的找法显然是一个简单二分，那么sum(dp[i2][j])显然就是一个前缀和
• 也就是说，在得到当前dp[i][j]的时候要维护一个第j列的前缀和，减少一层复杂度

ac code

提交的代码： 17 小时前
语言： python3

添加备注


class Solution:
    def beautifulPartitions(self, s: str, k: int, minLength: int) -> int:
        MOD = 10 ** 9 + 7
        n = len(s)
        primes = {'2', '3', '5', '7'}
        if s[0] not in primes or s[-1] in primes:
            return 0
        if k == 1:
            return int(s[0] in primes and s[-1] not in primes and len(s) >= minLength)
        # 可能的结束点j, 0 <= j < n - 1, j非质数 j + 1质数
        end_points = []
        for j, v in enumerate(s):
            if j < n - 1:
                if s[j] not in primes and s[j + 1] in primes:
                    end_points.append(j)
        #print(end_points)
        x = end_points
        m = len(end_points)
        if m < k - 1:
            return 0
        # 0 <= x1 < x2 < ... < xm <= n - 1 选k - 1个点
        # 不妨设为b1, b2, ... b(k - 1), 满足
        # 1.b1 + 1 >= minLength
        # 2.bi - b(i - 1) >= minLength, i belongs to [1, k - 1]
        # 3.n - 1 - b(k - 1) >= minLength
        # dp[i][j]表示第i个结束点作为第j个结束段点的个数
        # dp[i][k]求和，其中n - 1 - x[i] >= minLength
        dp = [[0] * (k - 1) for _ in range(m)]
        col_preSum = [[0] * (k - 1) for _ in range(m)] # 每列的前缀和优化
        for i in range(m): #init
            if x[i] + 1 >= minLength:
                #print(i, k, m)
                dp[i][0] = 1
            if i == 0:
                col_preSum[i][0] = dp[i][0]
            else:
                col_preSum[i][0] = col_preSum[i - 1][0] + dp[i][0]
         
        # 20221120我觉得大概能做出来把
        for i in range(m):
            for j in range(1, k - 1):
                # 本质上是一个j - 1列的前缀和
                # for i2 in range(i):
                #     if x[i] - x[i2] >= minLength:
                #         dp[i][j] += dp[i2][j - 1]
                #         dp[i][j] %= MOD
                check_point = x[i] - minLength
                i2 = bisect_right(x, check_point)
                if i2 == 0: # 找不到
                    dp[i][j] == 0
                else: # 找到
                    dp[i][j] += col_preSum[i2 - 1][j - 1]
                if i == 0:
                    col_preSum[i][j] = dp[i][j]
                else:
                    col_preSum[i][j] = col_preSum[i - 1][j] + dp[i][j]

        ans = 0
        for i in range(m):
            if n - 1 - x[i] >= minLength:
                ans += dp[i][-1]
                ans %= MOD
        return ans % MOD
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

总结

• 预处理找分割点 + dp定义二维 + 前缀和优化
• 从这道题我看到了自己的进步。。。