DP _ 1

# Restore the array

Example 1:

Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]
Example 2:

Input: s = "1000", k = 10
Output: 0
Explanation: There cannot be an array that was printed this way and has all integer >= 1 and <= 10.
Example 3:

Input: s = "1317", k = 2000
Output: 8
Explanation: Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]


code->>>>>

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
    
        # approach 1
        @lru_cache(None)
        def dfs(i):
            if i == len(s): return 1
            if s[i] == '0': return 0
            res, cur = 0, ''
            for j in range(i, len(s)):
                cur += s[j]
                if int(cur) > k: break
                res += dfs(j+1)
            return res % int(1e9 + 7)
        
        return dfs(0)

#---------------------------------------------------------------
           
        approach 2
        
        t = [-1] * len(s)
        
        def solve(start,s,k,t):
            n = len(s)
            if start == n:
                return 1
            if s[start] == '0':
                return 0
            if t[start] != -1:
                return t[start]
            ans = 0
            num = 0
            for end in range(start,n):
                num = (num*10) + int(s[end])
                if num > k:
                    break
                ans = (ans + solve(end + 1,s,k,t))%(10**9+7)

            t[start] = ans
            return ans
        
        return solve(0,s,k,t)