A die simulator generates a random number from 1 to 6 for each roll. You introduced a constraint to the generator such that it cannot roll the number i more than rollMax[i] (1-indexed) consecutive times.
Given an array of integers rollMax and an integer n, return the number of distinct sequences that can be obtained with exact n rolls.
Two sequences are considered different if at least one element differs from each other. Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: n = 2, rollMax = [1,1,2,2,2,3] Output: 34 Explanation: There will be 2 rolls of die, if there are no constraints on the die, there are 6 * 6 = 36 possible combinations. In this case, looking at rollMax array, the numbers 1 and 2 appear at most once consecutively, therefore sequences (1,1) and (2,2) cannot occur, so the final answer is 36-2 = 34.
Example 2:
Input: n = 2, rollMax = [1,1,1,1,1,1] Output: 30
Example 3:
Input: n = 3, rollMax = [1,1,1,2,2,3] Output: 181
Constraints:
1 <= n <= 5000rollMax.length == 61 <= rollMax[i] <= 15
Solutions: DP
Naive one:
def: dp[i][j][k] := # of sequences ends with k consecutive j after i rolls
Init: dp[1][*][1] = 1
transition:
dp[i][j][1] = sum(dp[i-1][p][*]), p != j
dp[i][j][k + 1] = dp[i-1][j]][k]
Time complexity: O(n*6*6*15)
Space complexity: O(n*6*15) -> O(6*15)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Author: Huahua class Solution { public: int dieSimulator(int n, vector<int>& rollMax) { constexpr int kMaxRolls = 15; constexpr int kMod = 1e9 + 7; // dp[i][j][k] := # of sequences ends with k consecutive j after i rolls vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(6, vector<int>(kMaxRolls + 1))); for (int j = 0; j < 6; ++j) dp[1][j][1] = 1; // 1 step, 1 dice, 1 way for (int i = 2; i <= n; ++i) for (int j = 0; j < 6; ++j) for (int p = 0; p < 6; ++p) for (int k = 1; k <= rollMax[p]; ++k) if (p != j) // not the same dice dp[i][j][1] = (dp[i][j][1] + dp[i - 1][p][k]) % kMod; else if (k < rollMax[p]) // same dice, make sure k + 1 <= rollMax dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][p][k]) % kMod; int ans = 0; for (int j = 0; j < 6; ++j) for (int k = 1; k <= rollMax[j]; ++k) ans = (ans + dp[n][j][k]) % kMod; return ans; } }; |
Solution 2: DP with compressed state
dp[i][j] := # of sequences of length i end with j
dp[i][j] := sum(dp[i-1]) – invalid
Time complexity: O(n*6)
Space complexity: O(n*6)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua class Solution { public: int dieSimulator(int n, vector<int>& rollMax) { constexpr int kMod = 1e9 + 7; // dp[i][j] := # of sequences ends with j after i rolls vector<vector<int>> dp(n + 1, vector<int>(7)); vector<int> sums(n + 1); // sums[i] := sum(dp[i]) for (int j = 0; j < 6; ++j) sums[1] += dp[1][j] = 1; // 1 roll, 1 dice, 1 way for (int i = 2; i <= n; ++i) for (int j = 0; j < 6; ++j) { const int k = i - rollMax[j]; const int invalid = k <= 1 ? max(k, 0) : sums[k - 1] - dp[k - 1][j]; dp[i][j] = ((sums[i - 1] - invalid) % kMod + kMod) % kMod; sums[i] = (sums[i] + dp[i][j]) % kMod; } return sums[n]; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment