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
Solution: DP
definition: dp[i][k] := ways to have sum of k using all first i dices.
Init: dp[0][0] = 1
transition: dp[i][k] = sum(dp[i – 1][k – j]), 1 <= j <= f
ans: dp[d][target]
Time complexity: O(|d|*|f|*target)
Space complexity: O(|d|*target) -> O(target)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua, 32ms, 10.8MB class Solution { public: int numRollsToTarget(int d, int f, int target) { constexpr int kMod = 1e9 + 7; vector<vector<int>> dp(d + 1, vector<int>(target + 1)); dp[0][0] = 1; for (int i = 1; i <= d; ++i) for (int j = 1; j <= f; ++j) for (int k = j; k <= target; ++k) dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % kMod; return dp[d][target]; } }; |
O(target)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua, 40 ms, 8.8MB class Solution { public: int numRollsToTarget(int d, int f, int target) { constexpr int kMod = 1e9 + 7; vector<int> dp(target + 1); dp[0] = 1; for (int i = 1; i <= d; ++i) for (int k = target; k >= 0; --k) { dp[k] = 0; for (int j = 1; j <= f && j <= k; ++j) dp[k] = (dp[k] + dp[k - j]) % kMod; } return dp[target]; } }; |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
# Author: Huahua from functools import lru_cache class Solution: def numRollsToTarget(self, d: int, f: int, target: int) -> int: mod = 10 ** 9 + 7 # Number of ways to have target t using i dices. @lru_cache(maxsize=None) def dp(i, t): if i == 0: return 1 if t == 0 else 0 # Pruning 388 ms -> 132 ms if t > f * i or t < i: return 0 ans = 0 for k in range(1, f + 1): ans = (ans + dp(i - 1, t - k)) % mod return ans return dp(d, target) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment