1155. Number of Dice Rolls With Target Sum

Python

Bottom Up DP

from functools import cache


class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        options = set([v for v in range(1, k+1)])
        mod = 10**9 + 7

        @cache
        def dp(i, total):
            if i == n:
                if total == target:
                    return 1
                return 0

            if total > target:
                return 0

            ans = 0
            for value in options:
                ans += dp(i+1, total+value)
            return ans % mod

        return dp(0, 0)