leetcode 1223

问题

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:

1
2
3
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:

1
2
Input: n = 2, rollMax = [1,1,1,1,1,1]
Output: 30

Example 3:

1
2
Input: n = 3, rollMax = [1,1,1,2,2,3]
Output: 181

Constraints:

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

分析

思路1: 使用带有记忆的dfs。先构建好dfs，然后使用memo进行优化。

思路2: 使用动态规划。$dp[i][j]$ 代表已经掷了 $i$ 次骰子，且最后一次点数是 $j$ 的序列有多少个。假设在没有限制的情况下，$ dp[i][j] = sum\{dp[i-1][k]\} \; (k\in[1,6])$，然后我们需要讲不合法的序列次数删除掉。假设 $j$ 连续出现的次数限制是 $rollMax[j]$ 那么就要删除掉，$ sum\{dp[i-rollMax[j]-1][k]\}\; k\in [1,6], but\; not \;j $ ，因为，之前连续出现了$rollMax[j]$ 次 $j$ 并且之前一个数又是 $j$ 的情况是不合法的已经被排除过了。$dp[i][6]$ 用来表示$sum$。

代码1

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
class Solution {
public:
    int dp[5000][6][16];
    int dieSimulator(int n, vector<int>& rollMax) {
        int ans = 0;
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < 6; ++i) {
            ans = (ans + dfs(rollMax, n-1, i, 1))%1000000007;
        }
        return ans;
    }
    int dfs(vector<int> &rollMax, int remaind, int last, int times) {
        if (remaind == 0)
            return 1;
        if (dp[remaind][last][times] != 0)
            return dp[remaind][last][times];
        int ans = 0;
        for (int n: {0,1,2,3,4,5}) {
            if (last == n) {
                if (times < rollMax[n]) {
                    ans = (ans + dfs(rollMax, remaind-1, n, times+1))%1000000007;
                }
            } else {
                ans = (ans + dfs(rollMax, remaind-1, n, 1))%1000000007;
            }
        }
        return dp[remaind][last][times] = ans;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    const int mod = 1000000007;
    int dieSimulator(int n, vector<int>& rollMax) {
        vector<vector<long long>> dp(n+1, vector<long long>(7, 0));
        dp[0][6] = 1;
        for (int i = 1; i <= n; ++i) {
            long long sum = 0;
            for (int j = 0; j < 6; ++j) {
                dp[i][j] = dp[i-1][6];
                if (i-rollMax[j]-1 >= 0) {
                    int p = i-rollMax[j]-1;
                    dp[i][j] = (dp[i][j]+mod - ((dp[p][6]+mod-dp[p][j]))%mod)%mod;
                }
                sum += dp[i][j];
            }
            dp[i][6] = sum%mod;
        }
        
        
        return dp[n][6];
    }
    
};