Python : Recursive solution fails due to massive test cases


#1

The following solution should work just fine. The TLE doesn’t make much sense here. Tried increasing the recursion limit to 1500, no luck with that as well. DP solution works just fine, however, recursive solutions look better imo.

import sys
class Solution:
    def __init__(self):
        self.first = True
        self.cache = {}
        self.grid = [[-1] * 1500 for _ in range(1500)]
        sys.setrecursionlimit(1500)
        
    # @param A : integer
    # @param B : integer
    # @return an integer
    def solve(self, n,s):
        if self.grid[n][s] != -1:
            return self.grid[n][s]
        
        if s==0:
            return 1
        
        if n==0:
            return (s==0)
    
        t = 0
        
        for i in range(10):
            if self.first:
                self.first = False
                continue
            if s-i >= 0:
                t += self.solve(n-1, s-i)
        
        self.grid[n][s] = t % 1000000007
        return t % 1000000007

#2

Try to solve from bottom to top.You can even get it in O(S) space, instead of O(n*S).


#3

@ [sahil-chaddha] Apparently the problem here is time and not space dude