LeetCode: Number of Dice Rolls With Target Sum

Posted on August 21, 2019July 26, 2020 by braindenny

Number of Dice Rolls With Target Sum

Similar Problems:

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.

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.

Constraints:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution:

// https://code.dennyzhang.com/number-of-dice-rolls-with-target-sum
// Basic Ideas: knapsack
// Complexity: Time O(d*f*target), Space O(target*d)
func numRollsToTarget(d int, f int, target int) int {
    if target < d || target > f*d {
        return 0
    }
        mod := 1000000007
    l := make([][]int, d)
    for i, _ := range l {
        l[i] = make([]int, target+1)
    }
    for i:=1; i<=target && i<=f; i++ {
        l[0][i] = 1
    }
    // add dices one by one
    for i:=1; i<d; i++ {
        // add face of one dice one by one
        for j:=1; j<=f; j++ {
            for k:=1; j+k<=target; k++ {
                // To get j+k: current j add previous k                 
                l[i][j+k] = (l[i][j+k]+l[i-1][k])%mod
            }
        }
    }
    return l[d-1][target]
}

// https://code.dennyzhang.com/number-of-dice-rolls-with-target-sum
// Basic Ideas: knapsack
// Complexity: Time O(d*f*target), Space O(target)
import "math"
func numRollsToTarget(d int, f int, target int) int {
    mod := int(math.Pow(10, 9))+7
    l := make([]int, target+1)
    for i:=1; i<=target && i<=f; i++ {
        l[i] = 1
    }
    // add dices one by one
    for i:=1; i<d; i++ {
        l2 := make([]int, len(l))
        // add face of one dice one by one
        for j:=1; j<=f; j++ {
            for k:=1; j+k<=target; k++ {
                l2[j+k]=(l2[j+k]+l[k])%mod
            }
        }
        copy(l, l2)
    }
    return l[target]
}

Post Views: 0