怎么做网页设计视频_平台型b2c平台有哪些_免费b站软件推广网站2023_seo托管

骰子模拟器：基于动态规划的点数序列计数问题解析

一、题目背景

在骰子模拟的世界中，有一个特殊的骰子模拟器。它每次投掷时会生成一个 1 到 6 的随机数，但存在一个约束条件：连续掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。现在给定一个整数数组 rollMax 和整数 n，要求计算掷 n 次骰子可得到的不同点数序列的数量（答案需对 10^9 + 7 取模）。

二、解题思路分析

动态规划（DP）核心逻辑：将复杂问题拆解为子问题，通过记录子问题的解避免重复计算。

状态定义：用三维数组 dp[i][j][k] 表示掷 i 次骰子，最后一次点数为 j（j∈[0,5]，对应 1-6 点），且 j 连续出现 k 次的序列数量。
初始化：当 i = 1 时，每个点数首次出现的情况各 1 种，即 dp[1][j][1] = 1。
状态转移：
- 情形一：当前点数首次连续出现（k = 1） dp[i][j][1] 可从前面任意非 j 的点数转移，即 dp[i][j][1] = Σ dp[i - 1][p][q]（p≠j，1≤q≤rollMax[p]）。
- 情形二：当前点数连续出现多次（k > 1） 仅能从 dp[i - 1][j][k - 1] 转移，需满足 k ≤ rollMax[j]。
结果计算：遍历所有 dp[n][j][k]（1≤k≤rollMax[j]）求和并取模。

三、代码实现与详解

class Solution {private static final int MOD = (int) (1e9 + 7);public int dieSimulator(int n, int[] rollMax) {int[][][] dp = new int[n + 1][6][16];// 初始化：第一次投掷，每个点数出现1次的情况for (int j = 0; j < 6; j++) {dp[1][j][1] = 1;}// 动态规划：从第2次投掷开始计算for (int i = 2; i <= n; i++) {for (int j = 0; j < 6; j++) {// 情形一：当前点数首次连续出现for (int p = 0; p < 6; p++) {if (p != j) {for (int q = 1; q <= rollMax[p]; q++) {dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][q]) % MOD;}}}// 情形二：当前点数连续出现多次for (int k = 2; k <= rollMax[j]; k++) {dp[i][j][k] = dp[i - 1][j][k - 1];}}}// 计算最终结果：汇总所有有效状态int 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;}
}

代码说明：

用 MOD 常量处理取模，dp 数组存储状态；
三层循环实现状态转移，内层分别处理两种情形；
最后两层循环累加 n 次投掷后的有效状态。

四、复杂度分析

时间复杂度： $O(n\times 6^{2}\times 15)$ （假设 rollMax 最大值为 15）；
空间复杂度： $O(n\times 6\times 15)$ ，取决于 dp 数组大小。

五、总结

通过动态规划，我们以状态转移精准解决了骰子序列计数问题。关键在于定义状态、拆解情形并严格取模。若对细节有疑问，欢迎随时交流！