Leetcode Problem 2318. Number of Distinct Roll Sequences

2318. Number of Distinct Roll Sequences

Leetcode Solutions

Top-Down Dynamic Programming with Memoization

  1. Initialize a 3D DP array dp with dimensions [n+1][7][7] filled with -1 to represent uncomputed states.
  2. Define a recursive function findSequences(index, last, prevLast) that returns the number of distinct sequences from the current index to n given the last two dice values last and prevLast.
  3. If index is n, return 1 as the base case.
  4. If dp[index][last][prevLast] is not -1, return its value as we have already computed this subproblem.
  5. Otherwise, iterate over all possible dice values from 1 to 6, and for each value i, check if it satisfies the conditions with last and prevLast. If it does, recursively call findSequences(index + 1, i, last) and add the result to the answer.
  6. Store the computed result in dp[index][last][prevLast] before returning it.
  7. Call findSequences(0, 0, 0) to get the total number of distinct sequences and return this value modulo 10^9 + 7.
UML Thumbnail

Bottom-Up Dynamic Programming with Optimized Space

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...