Leetcode 1155. Number of Dice Rolls With Target Sum

Problem statement

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

Solution 1

The idea is to have dp with state (n, total) and check what we can have on the last throw of dice.

Complexity

It is O(n * total * k) for time and O(n * total) for space.

Code

class Solution:
    def numRollsToTarget(self, n, k, total):
        @lru_cache(None)
        def dp(n, total):
            if total < n: return 0
            if total == n: return 1
            if n == 0: return total == 0
            return sum(dp(n - 1, total - x) for x in range(1, k + 1)) % (10**9 + 7)
        
        return dp(n, total)

Solution 2

In fact we can use some generation functions to get the direct answer:

\[\sum\limits_{k = 0}^{\inf} (-1)^k \cdot C_n^k \cdot C_{n - 1 + m - kf}^{n-1}.\]

Complexity

It is O(n + m) for time and space.

Code

MOD, M = 10**9 + 7, 1005
F = [1]*(M+1)
for i in range(1, M+1):
    F[i] = (F[i-1] * i) % MOD

I = [1]*M + [pow(F[M], MOD - 2, MOD)]
for i in range(M-1, 0, -1):
    I[i] = I[i+1]*(i+1) % MOD

class Solution:
    def numRollsToTarget(self, n, f, m):
        def ncr(n, r):
            if r < 0 or r > n: return 0
            return (F[n] * I[r] * I[n - r]) % MOD
        m -= n
        if m < 0 or m > n * (f - 1): return 0

        res = 0
        for i in range(n + 1):
            if m - i * f < 0: break
            cur = (ncr(n, i) * ncr(n + m - i * f - 1, n - 1)) % MOD
            sgn = -1 if i & 1 else 1
            res = (res + cur * sgn) % MOD

        return res