# 1416. Restore The Array
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/restore-the-array/
## 思路
令```dp[i]```表示以第```i```个数字结尾的array有多少种。只需要遍历最后一个number的范围```s[j:i]```（最多不超过10个digit）。只要```s[j:i]```符合题目的要求（没有leading zero、在```[1,k]```之间），那么就可以更新```dp[i]+=dp[j-1]```.
由于这题也要设置初始值这样就需要dp[1]对应到s[0], 考虑起来很麻烦 所以在s前面加了一个用来凑数的'#'([1043. Partition Array for Maximum Sum](https://hackmd.io/sSjKhGdcQrmWNvAvq0s6bw)和[1105. Filling Bookcase Shelves](https://hackmd.io/SStKMDA2S2OdA5X256a7KA)也是需要前面加一个凑数的的题)
## Code

class Solution {
    public int numberOfArrays(String s, int k) {
        int n = s.length();
        s = '#'+s;
        char[] charArr = s.toCharArray();
        long[] dp = new long[n+1];
        dp[0] = 1;
        int mod = 1000000007;
        for(int i=1; i<=n; i++){
            long val = 0;
            for(int j=i; j>=Math.max(1, i-9); j--){
                if(s.charAt(j)=='0') continue;
                val += Math.pow(10,i-j)*(s.charAt(j)-'0');
                if(val>=1 && val<=k) dp[i] = (dp[j-1]+dp[i])%mod;
                if(val>k) break;
            }
        }
        return (int)dp[n];
    }
}