Posted on 2023-04-23 21:11
Uriel 閱讀(48)
評論(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]