讨论/题目交流/🐱 第 24 场夜喵双周赛/
🐱 第 24 场夜喵双周赛
展开讨论

哪位大佬帮我看看第四题记忆化深搜为什么超时啊

class Solution:
    def numberOfArrays(self, s: str, k: int) -> int:
        
        #记忆化dfs mem中存除s有多少个,如果s在mem里直接返回个数
        self.mem=dict()
        
        def helper(s,k):
            #查找mem 
            if s in self.mem:
                return self.mem[s]
            #空s直接返回0
            if not s:
                return 0
            #0为先导的返回0
            if s[0]=='0':
                return 0
            #tmp计数
            tmp = 0
            #本身小于k 可以算1个
            if int(s)<=k:
                tmp += 1
                
            #剩下的逐个拆分dfs
            for i in  range(1,len(s)+1):
                #如果拆分出来的数小于k 那么进下一层
                if int(s[:i])<=k:
                    tmp = (tmp%(10**9+7)+ helper(s[i:],k)%(10**9+7))%(10**9+7)
            self.mem[s] = tmp
            return tmp
        
        return helper(s,k)
展开全部 32 讨论