Posted on 2023-04-23 21:11
Uriel 阅读(35)
评论(0) 编辑 收藏 引用 所属分类:
DP 、
闲来无事重切Leet Code
将一列字符串切分成若干子串，要求每个子串转为十进制数的数值位于[1, k]，问一共多少种切分方法，DP
1 #1416
2 #Runtime: 1325 ms (Beats 100%)
3 #Memory: 20 MB (Beats 25%)
4
5 class Solution(object):
6 def numberOfArrays(self, s, k):
7 """
8 :type s: str
9 :type k: int
10 :rtype: int
11 """
12 MOD = 10**9+7
13 n = len(s)
14 dp = [0] * (n + 1)
15 dp[n] = 1
16 for i in range(n - 1, -1, -1):
17 if s[i] == '0':
18 continue
19 t = 0
20 j = i + 1
21 while j <= n and int(s[i : j]) <= k:
22 t += dp[j]
23 j += 1
24 dp[i] = t % MOD
25 return dp[0]