Leetcode 1155. Number of Dice Rolls With Target Sum (Python)

Related Topic

Dynamic-Programming.

Description

You have d dice, and each die has f faces numbered 1, 2, …, f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Sample I/O

Example 1

Input: d = 1, f = 6, target = 3
Output: 1
Explanation: 
You throw one die with 6 faces.  There is only one way to get a sum of 3.

Example 2

Input: d = 2, f = 6, target = 7
Output: 6
Explanation: 
You throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:
1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3

Input: d = 2, f = 5, target = 10
Output: 1
Explanation: 
You throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.

Example 4

Input: d = 1, f = 2, target = 3
Output: 0
Explanation: 
You throw one die with 2 faces.  There is no way to get a sum of 3.

Example 5

Input: d = 30, f = 30, target = 500
Output: 222616187
Explanation: 
The answer must be returned modulo 10^9 + 7.

Note:

• 1 <= d, f <= 30
• 1 <= target <= 1000

Methodology

This question can be solved by Dynamic Programming.

First we need to know the maximum sum of all dice as upper bound and minimum sum of all dice as lower bound. If the target is out of range then return 0

This question can be simplyfy to you roll f faces dices d times.

Then we think about the base case, if we roll dice for only 1 time, then for any target in range, there is only 1 way to sum up to the target.

If we roll the dice more than 1 time, we go through from 1 to the target, find how many possible way to sum up to the tmp target.

Code

def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        mod = 10**9+7
        dp = [[0]*(target + 1) for _ in range(d + 1)]#dp[i][j] i: ith dices j: temp target
        dp[0][0] = 1
        if target < 1 or target > d*f: return 0
        for i in range(1, d + 1):
            for j in range(1, f + 1):
                for k in range(j, target + 1):
                    dp[i][k] = (dp[i][k] + dp[i-1][k-j]) % mod
        return dp[-1][-1]

BigO

Create dp list will cost O((target+1)*(d+1)) and iterate the dp will cost O(d*f*(target-f)) in total will be O(d*f*(target-f)+(target+1)*(d+1))