use dfs with memoization. state is (position, lastJump). from each stone, try jumps of lastJump-1, lastJump, lastJump+1. if we reach the last stone, return true.
memoization prevents revisiting the same (position, jump) states. use a set to track visited states and a set of valid stone positions for O(1) lookup.
key points
- first jump must be 1 (from position 0 to 1)
- subsequent jumps can vary by ±1 from previous jump
- memoize (position, lastJump) pairs to avoid redundant work
- early return when reaching the last stone
complexity
O(n²) worst case time with memoization, O(n²) space for visited set. each stone can be reached with different jump distances.