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] } Post Views: 0