1155. Number of Dice Rolls with Target Sum - Explanation

1. Recursion

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7

        def count(n, target):
            if n == 0:
                return 1 if target == 0 else 0
            if target < 0:
                return 0

            res = 0
            for val in range(1, k + 1):
                res = (res + count(n - 1, target - val)) % MOD
            return res

        return count(n, target)

Time & Space Complexity

Time complexity: $O(k ^ n)$
Space complexity: $O(n)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

2. Dynamic Programming (Top-Down)

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7
        cache = {}

        def count(n, target):
            if n == 0:
                return 1 if target == 0 else 0
            if (n, target) in cache:
                return cache[(n, target)]

            res = 0
            for val in range(1, k + 1):
                if target - val >= 0:
                    res = (res + count(n - 1, target - val)) % MOD
            cache[(n, target)] = res
            return res

        return count(n, target)

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(n * t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1

        for i in range(1, n + 1):
            for val in range(1, k + 1):
                for t in range(val, target + 1):
                    dp[i][t] = (dp[i][t] + dp[i - 1][t - val]) % MOD

        return dp[n][target]

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(n * t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

4. Dynamic Programming (Space Optimized)

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        MOD = 10**9 + 7

        for dice in range(n):
            next_dp = [0] * (target + 1)
            for val in range(1, k + 1):
                for total in range(val, target + 1):
                    next_dp[total] = (next_dp[total] + dp[total - val]) % MOD
            dp = next_dp

        return dp[target]

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.

5. Dynamic Programming (Optimal)

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7
        dp = [0] * (target + 1)
        dp[0] = 1

        for dice in range(n):
            for t in range(target, -1, -1):
                ways = dp[t]
                dp[t] = 0
                if ways:
                    for val in range(1, min(k + 1, target - t + 1)):
                        dp[t + val] = (dp[t + val] + ways) % MOD

        return dp[target]

Time & Space Complexity

Time complexity: $O(n * t * k)$
Space complexity: $O(t)$

Where $n$ is the number of dices, $k$ is the number of faces each dice have, and $t$ is the target value.