【动态规划-分组背包】力扣1155. 掷骰子等于目标和的方法数
这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kn 种方式），使得骰子面朝上的数字总和等于 target。
由于答案可能很大，你需要对 10^9 + 7 取模。
示例 1：
输入：n = 1, k = 6, target = 3
输出：1
解释：你掷了一个有 6 个面的骰子。
得到总和为 3 的结果的方式只有一种。
示例 2：
输入：n = 2, k = 6, target = 7
输出：6
解释：你掷了两个骰子，每个骰子有 6 个面。
有 6 种方式得到总和为 7 的结果: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1。
示例 3：
输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须对 109 + 7 取模。
提示：
1 <= n, k <= 30
1 <= target <= 1000
动态规划
static constexpr int MOD = 1e9+7;
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
vector<int> dp(target+1);
dp[0] = 1;
for(int i = 0; i < n; i++){
for(int j = target; j >= 0; j--){
dp[j] = 0;
for(int x = 1; x <= k; x++){
if(j >= x){
dp[j] = (dp[j] + dp[j-x]) % MOD;
}
}
}
}
return dp[target];
}
};
时间复杂度：O(n⋅k⋅target)，即为动态规划需要的时间。
空间复杂度：O(n⋅target) 或 O(target)，即为动态规划需要的空间。
分组背包：同一组内的物品至多/恰好选一个。
在这道背包问题中，采用了滚动数组的方式来优化空间。
首先我们先定义一个向量dp[j]，含义是目标和为j的时候的方案数。
然后初始化dp[0]=1。
首先我们先遍历每个骰子，也就是遍历i，然后接着倒序循环从target到0的目标和，并且在每次第二层循环的时候，令dp[j] = 0，最后循环骰子可能的点数x。
当我们已经确定了某个骰子i的时候，在他之前的前i-1个骰子，已经记录到了可能产生的目标和中，所以我们在计算第i个骰子可能产生的目标和的时候，是依赖于之前骰子产生的目标和。由于骰子只能投一次，且在下面的状态转移方程dp[j] = (dp[j] + dp[j-x]) % MOD;中，dp[j]代表的是可能产生的目标和，这取决于这次骰子的点数x，dp[j-x]取决于之前骰子产生的目标和。
我们需要注意的是，我们需要在计算产生的目标和j的方法数之前，令dp[j] = 0，使结果正确。这是因为当进入第 i 次投掷循环时，我们要重新计算所有可能的点数总和。每次投掷都会通过考虑当前骰子数（x）的影响，更新 dp[j]。如果不重置 dp[j]，它会保留前一次计算的值，从而导致错误的累积计算。
最后返回dp[target]即可。