leetcode题目数组篇（leetcode1155go掷骰子的N种方法）
这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, ..., f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），
模 10^9 7 后返回。
示例 1：输入：d = 1, f = 6, target = 3 输出：1
示例 2：输入：d = 2, f = 6, target = 7 输出：6
示例 3：输入：d = 2, f = 5, target = 10 输出：1
示例 4：输入：d = 1, f = 2, target = 3 输出：0
示例 5：输入：d = 30, f = 30, target = 500 输出：222616187
提示：1 <= d, f <= 30
1 <= target <= 1000
解题思路分析1、动态规划；时间复杂度O(n^3)，空间复杂度O(n)
func numRollsToTarget(d int, f int, target int) int {
dp := make([]int, target 1)
dp[0] = 1
for i := 0; i < d; i {
next := make([]int, target 1)
for j := 1; j <= f; j {
for k := 0; k <= target-j; k {
next[k j] = (next[k j] dp[k]) % 1000000007
}
}
dp = next
}
return dp[target]
}
2、动态规划；时间复杂度O(n^3)，空间复杂度O(n^2)
func numRollsToTarget(d int, f int, target int) int {
dp := make([][]int, d 1)
for i := 0; i <= d; i {
dp[i] = make([]int, target 1)
}
dp[0][0] = 1
for i := 1; i <= d; i {
for j := i; j <= target; j {
for k := 1; k <= f; k {
if j >= k {
dp[i][j] = (dp[i][j] dp[i-1][j-k]) % 1000000007
}
}
}
}
return dp[d][target]
}
Medium题目，动态规划题
,免责声明：本文仅代表文章作者的个人观点，与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺，请读者仅作参考，并自行核实相关内容。文章投诉邮箱：anhduc.ph@yahoo.com
