Problem statement

https://binarysearch.com/problems/Dice-Throw/

Solution

Equal to Leetcode 1155. Number of Dice Rolls With Target Sum.

Complexity

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

Code

class Solution:
    def solve(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)

Remark

There is also (n * total) time complexity solution if we precalculate prefix sums. There is also O(n + total) time complexity solution.