Two keys: overlapping subproblems (same state computed many times without memo) and an optimal substructure (the answer for N uses answers for smaller subproblems). If a recursive solution overlaps, DP is little more than adding a cache.
Fibonacci with memo: def f(n): return f(n-1)+f(n-2); add @lru_cache and it’s O(N).
Climbing stairs with K steps: f(n) = sum(f(n-k) for k in 1..K); cache the state.
Longest common subsequence: f(i,j) uses f(i-1,j-1), f(i-1,j), f(i,j-1).
House robber: f(i) = max(f(i-2) + house[i], f(i-1)).
recursive f(n) -> memoize -> tabulate -> O(N)
(overlap + optimal substructure = DP)DP “feels magical” until you see “overlapping subproblems + optimal substructure” twice in a row. Then it’s mechanical.