5375. 恢复数组


图片说明


简单递推

const mod int = 1000000007
func numberOfArrays(s string, m int) int {
    n:=len(s)
    var dp [100005]int
    dp[0]=1
    for i:=1;i<=n;i++{
        if(s[i-1]=='0'){
            continue
        }
        for j:=1;j<10;j++{
            if(i+j-1<=n){
                var ans int64 = 0
                for k:=i;k<=i+j-1;k++{
                    ans=ans*10+(int64)(s[k-1]-'0')
                }
                if(ans>(int64)(m)){
                    continue
                }
                dp[i+j-1]+=dp[i-1]
                dp[i+j-1]%=mod
            }
        }
    }
    return dp[n]
}