1155. 掷骰子的N种方法

我们的目标是掷骰子n次，获得target的总和的数量
这个问题是一个典型的 k 阶树，高度为n，即所有的解法为k^n种，但是明显的是，很多种解法是不必要的，因此第一个思路就是回溯剪枝，但是这里考虑使用dp的办法：

定义dp[i][j]为第i次投掷时，获得和为j的数量
遍历骰子可以投掷的范围[1..k]，第i次投掷得到骰子结果为k

• j - k > 0时，此时，意味着前 i-1次投掷得到的和j小于k，为j - k，因此应该找的是前面i-1次投掷中和为j-k的所有情况：dp[i][j] = dp[i-1][j - k]+...+dp[0][j-k]
• j - k = 0时，显然：dp[i][j] = 1
• j - k < 0时，显然此次不用计算，联合第一步考虑，就是只需要考虑到大小小于k的即可

初始化排除第二种情况
这道题其实也是分组背包
看三叶姐的题解

/**
 * 分组背包问题：掷骰子的N种方法
 */
private static int MOD = (int)1e9+7;
public int numRollsToTarget1(int n, int m, int target) {
    int[][] dp = new int[n + 1][target + 1];
    dp[0][0] = 1;// 考虑dp[1][1]的上一种情况就知道为啥了
    // 枚举物品组：骰子
    for (int i = 1; i <= n; i++) {
        // 枚举背包容量：总点数
        for (int j = 0; j <= target; j++) {
            // 枚举决策：当前骰子的点数
            for (int k = 1; k <= m; k++) {
                if (j - k >= 0)
                    dp[i][j] = (dp[i-1][j-k] + dp[i][j]) % MOD;
            }
        }
    }
    return dp[n][target];
}
// 优化：
public int numRollsToTarget(int n, int m, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    // 枚举物品组：骰子
    for (int i = 1; i <= n; i++) {
        // 枚举背包容量：总点数.注意要反过来，因为是要用到j-k的值
        for (int j = target; j >= 0; j--) {
            dp[j] = 0;          // 手动初始化为0，注意！！！
            // 枚举决策：当前骰子的点数
            for (int k = 1; k <= m; k++) {
                if (j - k >= 0)
                    dp[j] = (dp[j-k] + dp[j]) % MOD;
            }
        }
    }
    return dp[target];
}

上面是看为一个相同的骰子置m次的情况，因此看为一个树形的问题。但是上面的推导不是很清晰，看一下三叶姐的：

其实我可以学这种推导的方式，直接考虑f[i][j]然后查看上一次的情况，根据价值来判断。写出来就清晰很多：

impl Solution {
    pub fn num_rolls_to_target(n: i32, k: i32, target: i32) -> i32 {
        let (n, m, t) = (n as usize, k as usize, target as usize);
        let mut dp = vec![0; t + 1];
        dp[0] = 1;
        (1..=n).for_each(|i| {
            (0..=t).rev().for_each(|j| {
                dp[j] = 0;
                // 骰子的范围
                (1..=m).for_each(|k| {
                    if j >= k {
                        dp[j] = (dp[j - k] + dp[j]) % (1e9 as i32 + 7);
                    }
                });
            });
        });
        dp[t]
    }
}