Hard

题目描述

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。不过我们在使用它时有个约束，就是使得投掷骰子时，连续 投掷数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。

现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。

示例 1：

输入：n = 2, rollMax = [1,1,2,2,2,3]
输出：34
解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次，所以不能出现序列 (1,1) 和 (2,2)，因此最终答案是 36-2 = 34。

示例 2：

输入：n = 2, rollMax = [1,1,1,1,1,1]
输出：30

示例 3：

输入：n = 3, rollMax = [1,1,1,2,2,3]
输出：181

提示：

  • 1 <= n <= 5000
  • rollMax.length == 6
  • 1 <= rollMax[i] <= 15

解题思路

这是一道经典的动态规划问题，需要考虑状态转移时的连续性约束。

核心思路：

  • 定义状态：dp[i][j][k] 表示投掷了 i 次骰子，最后一个数字是 j+1，且这个数字连续出现了 k 次的方案数
  • 状态转移：
    1. 如果下一次投掷的数字与当前最后数字相同，则连续次数加1（需要检查是否超过限制）
    2. 如果下一次投掷的数字与当前最后数字不同，则连续次数重置为1

优化思路： 为了简化实现，我们可以使用二维DP：dp[i][j] 表示投掷了 i 次骰子，最后一个数字是 j 的所有合法方案数。然后通过减去不合法的方案来计算结果。

具体算法：

  1. dp[i][j] = 前 i 次投掷中最后一个数字是 j 的方案数
  2. 对于每个位置和每个数字，计算所有可能的转移
  3. 使用容斥原理，从总方案数中减去违反约束的方案数

时间复杂度：O(n × 6 × max(rollMax))，空间复杂度可以优化到 O(6 × max(rollMax))。

代码实现

class Solution {
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        const int MOD = 1e9 + 7;
        // dp[i][j][k] = 投掷i次，最后数字是j，连续出现k次的方案数
        vector<vector<vector<long long>>> dp(n + 1, vector<vector<long long>>(6, vector<long long>(16, 0)));
        
        // 初始化：第一次投掷
        for (int j = 0; j < 6; j++) {
            dp[1][j][1] = 1;
        }
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 6; j++) {
                // 情况1：当前数字j与上一个数字不同
                for (int prev = 0; prev < 6; prev++) {
                    if (prev != j) {
                        for (int k = 1; k <= rollMax[prev]; k++) {
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][prev][k]) % MOD;
                        }
                    }
                }
                
                // 情况2：当前数字j与上一个数字相同
                for (int k = 2; k <= rollMax[j]; k++) {
                    dp[i][j][k] = dp[i-1][j][k-1];
                }
            }
        }
        
        long long result = 0;
        for (int j = 0; j < 6; j++) {
            for (int k = 1; k <= rollMax[j]; k++) {
                result = (result + dp[n][j][k]) % MOD;
            }
        }
        
        return result;
    }
};

class Solution:
    def dieSimulator(self, n: int, rollMax: List[int]) -> int:
        MOD = 10**9 + 7
        # dp[i][j][k] = 投掷i次，最后数字是j，连续出现k次的方案数
        dp = [[[0] * 16 for _ in range(6)] for _ in range(n + 1)]
        
        # 初始化：第一次投掷
        for j in range(6):
            dp[1][j][1] = 1
        
        for i in range(2, n + 1):
            for j in range(6):
                # 情况1：当前数字j与上一个数字不同
                for prev in range(6):
                    if prev != j:
                        for k in range(1, rollMax[prev] + 1):
                            dp[i][j][1] = (dp[i][j][1] + dp[i-1][prev][k]) % MOD
                
                # 情况2：当前数字j与上一个数字相同
                for k in range(2, rollMax[j] + 1):
                    dp[i][j][k] = dp[i-1][j][k-1]
        
        result = 0
        for j in range(6):
            for k in range(1, rollMax[j] + 1):
                result = (result + dp[n][j][k]) % MOD
        
        return result

public class Solution {
    public int DieSimulator(int n, int[] rollMax) {
        const int MOD = 1000000007;
        // dp[i][j][k] = 投掷i次，最后数字是j，连续出现k次的方案数
        long[,,] dp = new long[n + 1, 6, 16];
        
        // 初始化：第一次投掷
        for (int j = 0; j < 6; j++) {
            dp[1, j, 1] = 1;
        }
        
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 6; j++) {
                // 情况1：当前数字j与上一个数字不同
                for (int prev = 0; prev < 6; prev++) {
                    if (prev != j) {
                        for (int k = 1; k <= rollMax[prev]; k++) {
                            dp[i, j, 1] = (dp[i, j, 1] + dp[i-1, prev, k]) % MOD;
                        }
                    }
                }
                
                // 情况2：当前数字j与上一个数字相同
                for (int k = 2; k <= rollMax[j]; k++) {
                    dp[i, j, k] = dp[i-1, j, k-1];
                }
            }
        }
        
        long result = 0;
        for (int j = 0; j < 6; j++) {
            for (int k = 1; k <= rollMax[j]; k++) {
                result = (result + dp[n, j, k]) % MOD;
            }
        }
        
        return (int)result;
    }
}

var dieSimulator = function(n, rollMax) {
    const MOD = 1e9 + 7;
    // dp[i][j][k] = 投掷i次，最后数字是j，连续出现k次的方案数
    const dp = Array(n + 1).fill(null).map(() => 
        Array(6).fill(null).map(() => Array(16).fill(0))
    );
    
    // 初始化：第一次投掷
    for (let j = 0; j < 6; j++) {
        dp[1][j][1] = 1;
    }
    
    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < 6; j++) {
            // 情况1：当前数字j与上一个数字不同
            for (let prev = 0; prev < 6; prev++) {
                if (prev !== j) {
                    for (let k = 1; k <= rollMax[prev]; k++) {
                        dp[i][j][1] = (dp[i][j][1] + dp[i-1][prev][k]) % MOD;
                    }
                }
            }
            
            // 情况2：当前数字j与上一个数字相同
            for (let k = 2; k <= rollMax[j]; k++) {
                dp[i][j][k] = dp[i-1][j][k-1];
            }
        }
    }
    
    let result = 0;
    for (let j = 0; j < 6; j++) {
        for (let k = 1; k <= rollMax[j]; k++) {
            result = (result + dp[n][j][k]) % MOD;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n × 6 × max(rollMax)) = O(n × 6 × 15) = O(90n)
空间复杂度O(n × 6 × max(rollMax)) = O(90n)，可优化至 O(6 × max(rollMax))

相关题目