1416. Restore The Array

https://leetcode.com/problems/restore-the-array/

目前的解法在leetcode里TLE但是合理的dp with cache的解法

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        self.cache = dict()
        mod = 10**9+7
        def dp(s):
            if s == "":
                return 1
            if s[0] == "0":
                return 0
            if s in self.cache:
                return self.cache[s]
            cnt = 0
            for i in range(1,min(len(s)+1,len(str(k))+1)):
                curr = int(s[:i])
                if curr > k:
                    break
                cnt += dp(s[i:]) % mod
            self.cache[s] = cnt
            return cnt % mod
        #print(self.cache)
        return dp(s)