Hi everyone,
I'm trying to solve LeetCode's "Snakes and Ladders" using DFS with memoization (dp[square] for min moves) and a visited_in_path[square] check to prevent infinite loops if square is already in the current recursion stack.
However, for some test cases, my DFS outputs a suboptimal path (e.g., 4 moves when 3 is expected).
My Core Confusion:
I understand visited_in_path stops simple stack overflow cycles like A → B → A. But I'm struggling to see exactly how this check causes my dp values for some squares to become permanently suboptimal, leading to a longer overall path found.
Specifically, can the true shortest path for a subproblem (e.g., from square X) sometimes require taking a snake or ladder to an Ancestor square (where Ancestor is still active higher up in dfs(X)'s current call stack)? If so, my visited_in_path[Ancestor] check would prune this path segment for X. How does this pruning specifically lead to dp[X] (and subsequently dp[Start_Square]) being wrong, rather than just avoiding a simple loop? I'm looking for a clear, minimal example that demonstrates how pruning based on an active ancestor in visited_in_path results in an incorrect dp value for an intermediate square, making the final answer suboptimal. Why isn't the first time dp[square] is fully computed always the true shortest path from that square with this DFS strategy?
