Leetcode Problem 2400. Number of Ways to Reach a Position After Exactly k Steps

2400. Number of Ways to Reach a Position After Exactly k Steps

Leetcode Solutions

Dynamic Programming with Memoization

  1. Define a memoization table dp with dimensions [k+1][2*max(startPos, endPos, k)+1] to handle negative indices.
  2. Initialize all values in dp to -1, representing uncomputed states.
  3. Define a recursive function solve that takes the current position, the end position, the number of steps remaining, and the memoization table as arguments.
  4. If the number of steps is zero, check if the current position is the end position. If so, return 1; otherwise, return 0.
  5. If the result for the current state is already in the memoization table, return it.
  6. Otherwise, recursively call solve for one step to the left and one step to the right, sum the results, take modulo 10^9+7, and store it in the memoization table.
  7. Return the result from the memoization table for the initial state.
UML Thumbnail

Combinatorics Approach

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...