資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：計算將數字字串拆分為列表的方案數
假設我們有一個字串 s。s 包含數字 0 到 9，我們還有一個數字 k。我們需要找到 s 可以表示為 [1, k] 中數字列表的不同方式的數量。如果答案非常大，則返回結果模 10^9 + 7。
因此，如果輸入類似於 s = "3456" k = 500，則輸出將為 7，因為我們可以將 s 表示為 [3, 4, 5, 6]、[34, 5, 6]、[3, 4, 56]、[3, 45, 6]、[34, 56]、[345, 6]、[3, 456]
為了解決這個問題，我們將遵循以下步驟：
m := 10^9 + 7
N := s 的大小
dp := 大小為 (N + 1) 的列表，並填充 0
dp[N] := 1
對於 i 從 N − 1 到 0，遞減 1，執行以下操作：
curr_val := 0
對於 j 從 i 到 N，執行以下操作：
curr_val := curr_val * 10 + (s[j] 作為數字)
如果 curr_val 在 1 到 k 的範圍內，則
dp[i] :=(dp[i] + dp[j + 1]) mod m
否則，
退出迴圈
返回 dp[0]
讓我們看看以下實現以更好地理解：
示例
class Solution: def solve(self, s, k): m = 10 ** 9 + 7 N = len(s) dp = [0] * (N + 1) dp[N] = 1 for i in range(N − 1, −1, −1): curr_val = 0 for j in range(i, N): curr_val = curr_val * 10 + int(s[j]) if 1 <= curr_val <= k: dp[i] = (dp[i] + dp[j + 1]) % m else: break return dp[0] ob = Solution() s = "3456" k = 500 print(ob.solve(s, k))
輸入
"3456", 500
輸出
7
更新於： 2020-12-26
79 次瀏覽
廣告