Medium

题目描述

你有 n 个骰子，每个骰子有 k 个面，分别标有 1 到 k 的数字。

给定三个整数 n、k 和 target，返回可能的方法数（在总共 k^n 种方法中），使得掷出的点数和恰好等于 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
解释：答案必须对 10^9 + 7 取余。

约束条件：

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

提示：

  • 使用动态规划。状态是剩余多少个骰子，以及到目前为止掷出的总和。

解题思路

这是一道经典的动态规划问题。我们需要计算使用 n 个骰子掷出目标和的方法数。

核心思路： 定义状态 dp[i][j] 表示使用 i 个骰子掷出和为 j 的方法数。

状态转移方程： 对于第 i 个骰子，我们可以掷出 1 到 k 的任意点数，因此：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][j-k]

其中 j-face >= 0 且 j-face <= target。

边界条件：

  • dp[0][0] = 1：使用 0 个骰子得到和为 0 的方法数为 1
  • 其他 dp[0][j] = 0：使用 0 个骰子无法得到非零和

优化：

  1. 可以使用滚动数组优化空间复杂度
  2. 提前判断不可能的情况：如果 target < n 或 target > n*k，直接返回 0

实现细节：

  • 记得对 10^9 + 7 取余
  • 可以从后往前更新状态，避免使用额外空间

代码实现

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        const int MOD = 1e9 + 7;
        
        // 不可能的情况
        if (target < n || target > n * k) return 0;
        
        vector<vector<int>> dp(n + 1, vector<int>(target + 1, 0));
        dp[0][0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                for (int face = 1; face <= k && face <= j; face++) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD;
                }
            }
        }
        
        return dp[n][target];
    }
};

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        MOD = 10**9 + 7
        
        # 不可能的情况
        if target < n or target > n * k:
            return 0
        
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        
        for i in range(1, n + 1):
            for j in range(1, target + 1):
                for face in range(1, min(k + 1, j + 1)):
                    dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD
        
        return dp[n][target]

public class Solution {
    public int NumRollsToTarget(int n, int k, int target) {
        const int MOD = 1_000_000_007;
        
        // 不可能的情况
        if (target < n || target > n * k) return 0;
        
        int[,] dp = new int[n + 1, target + 1];
        dp[0, 0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= target; j++) {
                for (int face = 1; face <= k && face <= j; face++) {
                    dp[i, j] = (dp[i, j] + dp[i-1, j-face]) % MOD;
                }
            }
        }
        
        return dp[n, target];
    }
}

var numRollsToTarget = function(n, k, target) {
    const MOD = 1e9 + 7;
    
    // 不可能的情况
    if (target < n || target > n * k) return 0;
    
    const dp = Array(n + 1).fill(null).map(() => Array(target + 1).fill(0));
    dp[0][0] = 1;
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= target; j++) {
            for (let face = 1; face <= k && face <= j; face++) {
                dp[i][j] = (dp[i][j] + dp[i-1][j-face]) % MOD;
            }
        }
    }
    
    return dp[n][target];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n × target × k)三重循环遍历所有状态和转移
空间复杂度O(n × target)二维DP数组存储状态

备注： 可以使用滚动数组将空间复杂度优化到 O(target)，但代码复杂度会增加。

相关题目