1977. 划分数字的方案数

1977. 划分数字的方案数

解题思路

power by @jia-zhi-tong-1
平方时间复杂度的动态规划解法（无需预处理和前缀和）
做了详细的注释
另外写了个超时的函数供理解问题

代码

class Solution:
    def numberOfCombinations(self, num: str) -> int:
        if num[0] == '0': return 0
        MX = 10**9 + 7
        # return combine(num, 0, 1) % MX

        # i:截至i的前缀
        # j:最后一个数字的长度
        # dp[i][j]表示以第i位结尾长度为j的划分数
        
        N = len(num)
        dp = [[0 for _ in range(N+1)] for _ in range(N)]
        
        dp[0][1] = 1                            # 以num[0]结尾长度为1的情形
        for i in range(1, N):
            dp[i][i+1] = 1                      # 整个串就一个数字
            for j in range(1, i+1):             # for最后一个数字的长度
                if num[i-j+1] == '0': continue  # 第一个字符不能为'0'
                dp[i][j] += dp[i-1][j-1]        # 最后一个字符给最后一个数字
                                                # end为倒数第二个数字的结尾位置
                                                # end+1为倒数第一个数字的开始位置
                end = i - j                     # 下面if条件的前半部分只是为了约束长度足够j-1和j
                if end >= j-2 and num[end-j+2:end+1] > num[end+1:i]:
                    dp[i][j] += dp[end][j-1]    # 长度都为j-1, 前一个大于后一个,说明没有被dp[i-1][j-1]包含
                if end >= j-1 and num[end-j+1:end+1] <= num[end+1:i+1]:
                    dp[i][j] += dp[end][j]      # 长度都为j,前一个小于等于后一个,应该包含进来
        
        return sum(dp[-1]) % MX


"""
def combine(num, start, mi):
    if start >= len(num): return 1
    if num[start] == '0': return 0
    
    ans = 0
    i = len(num)
    v = int(num[start:i])
    while i > start:
        if i != len(num):
            v //= 10
        if v < mi: break
        ans += combine(num, i, v)
        i -= 1

    return ans
"""