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)