Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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:

  • CheatSheet: Leetcode For Code Interview
  • CheatSheet: Common Code Problems & Follow-ups
  • Tag: #knapsack

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]
}

linkedin
github
slack

Post Views: 0
Posted in MediumTagged knapsack

Post navigation

LeetCode: Product Price at a Given Date
LeetCode: Reconstruct Itinerary

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.