题目描述
有n个一样的骰子，他们有f面（即骰子的点数从1到f），问投掷这些骰子和为target的概率为多少？
注意
不能使用回溯
题解
这是一道经典的背包问题。背包问题的详解可以看本网站的这一篇博客->背包问题详解
该题目是一个分组背包，只需要在0/1背包基础上加上一层循环遍历每一个分组即可
long long mod = 1e9 + 7;
int numRollsToTarget(int n, int f, int target) {
vector<vector<long long>> dp(n + 1, vector<long long>(target + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= f; j++) {
for (int k = target; k >= j; k--) {
dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % mod;
}
}
}
return dp[n][target];
}