難度: Hard
目前下列解法的時間複雜度: O(n) ( O(n)*lg(k) ,但k<=1e9且底數是10且是簡單迴圈 )
題目說明
給一分隔符號不見了的正整數陣列,以字串表達 (長度為 n) ,以及一個 k ,代表原本陣列中的數字都在 [1,k] 之間,
問原本的陣列有幾種可能。
解法 dp
0. dp[只用在此之前的數字] -> 答案 = sum(dp[此格-前一個數字位數] if 該數字符合條件)
1. 想法上先著重在"加入最後一個數字時"。
2. 若最後一個數字符合在區間 [1,k] 內的這個條件,則最後一個數字再往前1格的答案可以加進來。
3. 所以總共枚舉10個數字,執行上述,加起來填答案,填到底回傳答案。
4. 計算答案時記得依題目要求 mod 1000000007
source code