掷骰子的N种方法

1155. 掷骰子的N种方法

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n , k 和 target ，返回可能的方式(从总共 kⁿ 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。

答案可能很大，你需要对 10⁹ + 7 取模。

示例 1：

输入：n = 1, k = 6, target = 3
输出：1
解释：你扔一个有6张脸的骰子。
得到3的和只有一种方法。

示例 2：

输入：n = 2, k = 6, target = 7
输出：6
解释：你扔两个骰子，每个骰子有6个面。
得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。

示例 3：

输入：n = 30, k = 30, target = 500
输出：222616187
解释：返回的结果必须是对 10⁹ + 7 取模。

提示：

1 <= n, k <= 30
1 <= target <= 1000

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int numRollsToTarget(int n, int k, int target) { } };

cpp 解法, 执行用时: 48 ms, 内存消耗: 6.6 MB, 提交时间: 2023-10-24 07:40:09

class Solution {
public:
    // f(i,j) 表示使用 i 个骰子且数字之和为 j 的方案数。
    int numRollsToTarget1(int n, int k, int target) {
        vector<vector<int>> f(n + 1, vector<int>(target + 1));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= target; ++j) {
                for (int x = 1; x <= k; ++x) {
                    if (j - x >= 0) {
                        f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod;
                    }
                }
            }
        }
        return f[n][target];
    }

    // 降维优化, f(i, j)只会从f(i-1, ...)转化, 用两个一维数组代替二维数组 f 进行状态转移。
    int numRollsToTarget2(int n, int k, int target) {
        vector<int> f(target + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            vector<int> g(target + 1);
            for (int j = 0; j <= target; ++j) {
                for (int x = 1; x <= k; ++x) {
                    if (j - x >= 0) {
                        g[j] = (g[j] + f[j - x]) % mod;
                    }
                }
            }
            f = move(g);
        }
        return f[target];
    }
    
    // 
    int numRollsToTarget(int n, int k, int target) {
        vector<int> f(target + 1);
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = target; j >= 0; --j) {
                f[j] = 0;
                for (int x = 1; x <= k; ++x) {
                    if (j - x >= 0) {
                        f[j] = (f[j] + f[j - x]) % mod;
                    }
                }
            }
        }
        return f[target];
    }




private:
    static constexpr int mod = 1000000007;
};

rust 解法, 执行用时: 4 ms, 内存消耗: 2.1 MB, 提交时间: 2023-10-24 07:25:10

impl Solution {
    pub fn num_rolls_to_target(d: i32, f: i32, target: i32) -> i32 {
        if target < d || target > d * f {
            return 0;
        }

        let d = d as usize;
        let f = f as usize;
        let target = target as usize;
        let mut dp = vec![vec![0; target + 1]; d + 1];
        dp[0][0] = 1;

        for i in 0..d {
            for j in i.max(target.saturating_sub((d - i) * f))..=(i * f).min(target - d + i) {
                for k in 1..=f.min(target - j) {
                    dp[i + 1][j + k] += dp[i][j];
                    dp[i + 1][j + k] %= 1_000_000_007;
                }
            }
        }

        dp[d][target]
    }
}

python3 解法, 执行用时: 960 ms, 内存消耗: 16.6 MB, 提交时间: 2023-05-30 09:49:07

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        #动态规划  背包问题
        dp = [[0 for _ in range(target + 1)] for _ in range(d + 1)]
        dp[0][0] = 1
        for i in range(1, d + 1):           #虚指
            for j in range(i, target + 1):  #因为投出来的最小数是1
                for k in range(1, min(f, j) + 1):   #第i个扔出来的值
                    dp[i][j] += dp[i-1][j-k]
                    dp[i][j] %= 1000000007
        return dp[d][target]

python3 解法, 执行用时: 196 ms, 内存消耗: 16.7 MB, 提交时间: 2023-05-30 09:48:40

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        dp = [[0]*(target+1) for i in range(n+1)]  #dp[k][target]扔了n次，和为target
        for i in range(1,min(k+1,target+1)):
            dp[1][i] = 1
        for i in range(2,n+1):
            for summ in range(i,min(target+1,k*i+1)):
                dp[i][summ] = (sum(dp[i-1][summ-k] for k in range(1,min(k+1,summ+1))))%(10**9+7)
        return dp[n][target]

golang 解法, 执行用时: 8 ms, 内存消耗: 1.9 MB, 提交时间: 2023-05-30 09:47:58

func numRollsToTarget(n int, k int, target int) int {
    if target < n || n * k < target {
        return 0
    }
    var mod = int(1e9 + 7)
    //dp[i] 表示凑成 i 有多少种方法
    dp := make([]int, target + 1)
    //凑成 0 有 1 种方法
    dp[0] = 1

    //先遍历物品
    for i := 0; i < n; i++ {
        //再遍历背包
        for j := target; j >= 0; j-- {
            //此处置零
            dp[j] = 0
            //再遍历每个物品的决策
            for l := 1; l <= k; l++ {
                if j >= l {
                    //方案数为选择1~6的答案累加
                    dp[j] = (dp[j] + dp[j - l]) % mod
                }
            }
        }
    }
    return dp[target]
}

java 解法, 执行用时: 22 ms, 内存消耗: 38.2 MB, 提交时间: 2023-05-30 09:47:20

class Solution {
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int m, int t) {
        int[] f = new int[t + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = t; j >= 0; j--) {
                f[j] = 0;
                for (int k = 1; k <= m; k++) {
                    if (j >= k) {
                        f[j] = (f[j] + f[j-k]) % mod;
                    }
                }
            }
        } 
        return f[t];
    }
}

java 解法, 执行用时: 23 ms, 内存消耗: 39.6 MB, 提交时间: 2023-05-30 09:46:55

class Solution {
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int m, int t) {
        int[][] f = new int[n + 1][t + 1];
        f[0][0] = 1;
        // 枚举物品组（每个骰子）
        for (int i = 1; i <= n; i++) {
            // 枚举背包容量（所掷得的总点数）
            for (int j = 0; j <= t; j++) {
                // 枚举决策（当前骰子所掷得的点数）
                for (int k = 1; k <= m; k++) {
                    if (j >= k) {
                        f[i][j] = (f[i][j] + f[i-1][j-k]) % mod;
                    }
                }
            }
        } 
        return f[n][t];
    }
}

java 解法, 执行用时: 8 ms, 内存消耗: 38.5 MB, 提交时间: 2023-05-30 09:45:54

/**
1.首先判断下特殊情况, 我们知道扔完n个k面骰后的数值范围在n到n*k之间
如果target > n * k 或者 target < n, 那么target的结果一定为0

2.创建一个数组, 用来统计在第i轮情况下, 得到每一个数值的方法有多少种
我们可以通过当前这一轮的数据, 推算出下一轮各个数值的方法个数

3.下一轮的最大数值为(a + 1) * k, 那么我们开一个大小为(a + 1) * k的数组

4.当前这一轮的有效数值范围为 a 到 a * k, 那么在当前数值情况下, 新的骰子可能为1到k
所以new_count[b + (1到k)] += count[b]; new_count[b + c] %= mod;

5.在结束后我们将count = new_count;

6.最后返回(int)count[target]即可
 **/
class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        if(target > n * k || target < n){
            return 0;
        }

        int mod = (int)1e9 + 7;
        long[] count = new long[k + 1];

        for(int i = 1; i <= k; i++){
            count[i] = 1;
        }

        for(int a = 1; a < n; a++){
            long[] new_count = new long[(a + 1) * k + 1];
            for(int b = a; b <= a * k; b++){
                for(int c = 1; c <= k; c++){
                    new_count[b + c] += count[b];
                    new_count[b + c] %= mod;
                }
            }

            count = new_count;
        }

        return (int)count[target];
    }
}

java 解法, 执行用时: 18 ms, 内存消耗: 41.9 MB, 提交时间: 2023-05-30 09:44:16

/**
 * 动态规划
 * 状态：dp[i][j] 代表 扔 i 个骰子和为 j；
 * 方程：dp[i][j] 与 dp[i - 1] 的关系是什么呢？ 第 i * 次我投了 k ( 1 <= k <= f)，
 * 那么前 i - 1 次 和 为 j - k，对应 dp[i - 1][j - k]；
 * 于是有最终方程：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j - 2] + ... + dp[i - 1][j - f]
 * 边界条件： dp[1][k] = 1 ( 1<= k <= min(target, f) )
 **/

class Solution {
  private static final int MOD = 1000000007;
  public int numRollsToTarget(int d, int f, int target) {
    int[][] dp = new int[31][1001];
    int min = Math.min(f, target);
    for (int i = 1; i <= min; i++) {
      dp[1][i] = 1;
    }
    int targetMax = d * f;
    for (int i = 2; i <= d; i++) {
      for (int j = i; j <= targetMax; j++) {
        for (int k = 1; j - k >= 0 && k <= f; k++) {
          dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
        }
      }
    }
    return dp[d][target];
  }
}

上一题

下一题

详情