Wait, Is This Actually DP? A Conversation About Memoization
· 10 min read
A casual conversation between two software engineers about the subtle differences between recursion, memoization, and "real" DP.
The Setup
It's late afternoon at the office. Alex just finished implementing a memoized solution to Min Cost Climbing Stairs and walks over to Jamie's desk with their laptop.
Alex: Hey Jamie, can I bug you for a second? I'm confused about something with DP.
Jamie: [looks up from code review] Sure, what's up?
Alex: So I wrote this solution for the climbing stairs problem. I started with recursion, then added memoization like everyone says. But now I'm wondering... is this actually DP? Or is it still just recursion?