1155. Number of Dice Rolls With Target Sum

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

Number of Dice Rolls With Target Sum - LeetCode

tweaked target sum

 

456ms

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        
        dp = [0] * (target + 1)
        for n in range(1, min(f+1, target+1)):
            dp[n] = 1
        
        for _ in range(d-1):
            _dp = [0] * (target+1)
            for i in range(1, target+1):
                if dp[i] <= 0:
                    continue
                for j in range(1, f+1):
                    if i+j > target:
                        continue
                    _dp[i+j] += dp[i]
                    _dp[i+j] %= 10**9+7
            dp = _dp.copy()
        return dp[target]

32ms

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        
        return sum([(-1) ** i * comb(d, i) * comb(target - i*f - 1, d-1) for i in range(1 + (target - d) // f)]) % 1000000007