1223. Dice simulation range DP

1223. Roll the dice to simulate

There is a dice simulator that generates a... Every time you roll 1 To 6 The random number .

But we have a constraint when using it , Is to make the dice roll , continuity   Throw a number  i  You can't do more than  rollMax[i]（i  from 1 Numbered starting ）.

Now? , Give you an array of integers  rollMax  And an integer  n, Please count the roll  n  The number of different point sequences that can be obtained from one dice .

If at least one element in two sequences is different , I think the two sequences are different . Because the answer can be big , So please return to   model  10^9 + 7  Later results .

Example 1：

 Input ：n = 2, rollMax = [1,1,2,2,2,3]
 Output ：34
 explain ： We throw  2  Second dice , If there are no constraints , share  6 * 6 = 36  A possible combination . But according to  rollMax  Array , Numbers  1  and  2  At most once in a row , So there will be no sequence  (1,1)  and  (2,2). therefore , 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

Tips ：

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

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/dice-roll-simulation
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

Failure , This type of dp It feels particularly difficult , I can't find the feeling after writing several times , The foundation of mathematics may be more important

Method ： Dynamic programming

Reference resources ：https://leetcode.cn/problems/dice-roll-simulation/solution/java-2wei-dp-by-zdxiq125/

1. Suppose the number of quantity elements in front is insufficient , There is no need to deal with , Throw all the previous results directly to 1 To 6 Accumulation

2. Suppose you just step on the edge of the limit , For example, there can only be 3 individual 3, Now it happens to be 4 Number , Then remove the first one 3 The situation of ,3 3 3 3 

3. Suppose there is 5 Number , b a 3 3 3, that a It can be any other number , But it can't be 3, stay a No 3 The situation of , Push to the first 3, In order to properly remove , Because this is the only case ,a 3 3 3, First of all 3 Can guarantee to be the first , Arbitrary non 3 Add a after the number 3, Can guarantee this 3 It is the first of this continuous segment 3, Note that we cannot start directly from the first 3 Start pushing , Because this and may contain this 3 Is the first , the second 3 The situation of , These situations are legal . So this part needs to be preceded by a number non 3 And derived .

class Solution {
      public int dieSimulator(int n, int[] rollMax) {
          long MOD = (long) (1e9+7);
          long[][] dp = new long[n+1][6];
          Arrays.fill(dp[1],1);
          for(int i = 2; i <= n; i++){
              for(int j=0; j < 6; j++){
                  for(int k = 0; k < 6; k++){
                      dp[i][j] = (dp[i][j]+dp[i-1][k])%MOD;
                  }

                  if(i-rollMax[j]-1==0){
                      --dp[i][j];
                  }else if(i-rollMax[j]-1>0){
                      for(int k = 0; k < 6; k++){
                          if(k!=j){
                              dp[i][j] = (dp[i][j]-dp[i-rollMax[j]-1][k]+MOD)%MOD;
                          }
                      }
                  }
              }
          }

          long sum = 0;
          for(int i = 0; i < 6; i++){
              sum += dp[n][i];
              sum = sum %MOD;
          }
          return (int)sum;
      }
  }