Leetcode Problem 1223. Dice Roll Simulation

1223. Dice Roll Simulation

Leetcode Solutions

Dynamic Programming Approach

  1. Initialize a 3D array dp of size n+1 x 6 x max(rollMax)+1 with all elements set to 0.
  2. Set dp[0][i][0] to 1 for all i from 0 to 5, representing the base case of having 0 rolls.
  3. Iterate over the sequence length i from 1 to n.
  4. For each sequence length i, iterate over the last number j from 1 to 6.
  5. For each last number j, iterate over the count k from 1 to rollMax[j-1].
  6. Add the number of sequences of length i-1 that can end with any number except j to dp[i][j][1].
  7. For counts k greater than 1, set dp[i][j][k] to dp[i-1][j][k-1].
  8. Calculate the total number of sequences of length i by summing up all dp[i][j][k] values and take modulo 10^9+7.
  9. The answer is the sum of all dp[n][j][k] values for all j and k.
UML Thumbnail

Recursive Approach with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...