Leetcode Problem 935. Knight Dialer

935. Knight Dialer

Leetcode Solutions

Approach: Top-Down Dynamic Programming

  1. Define a 2d array jumps where jumps[square] contains a list of all squares that you can jump to from square.
  2. Define a memoized function dp(remain, square):
    • If remain == 0, return 1.
    • Initialize ans = 0.
    • Iterate nextSquare over jumps[square]:
      • Add dp(remain - 1, nextSquare) to ans.
    • Return ans.
  3. Initialize ans = 0.
  4. Iterate square from 0 to 9:
    • Add dp(n - 1, square) to ans.
  5. Return ans.
UML Thumbnail

Approach: Bottom-Up Dynamic Programming

Ask Question

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

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...