1155. Number of Dice Rolls With Target Sum - LeetCode Solution

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:

        dp = []


        for i in range(d+1):
            a = []
            for j in range(target+1):
                a.append(-1)
            dp.append(a)



        def trav(d, f, target):
            if target == 0 and d == 0:
                return 1

            if target <= 0 or d<= 0:
                return 0


            if dp[d][target] != -1:
                return dp[d][target]

            dp[d][target] = 0

            for i in range(1, f+1, 1):
                dp[d][target] += trav(d-1, f, target - i)

            return dp[d][target]

        return trav(d, f, target)%(10**9 + 7)