This is the first part of a series where I’ll share what I’ve learned about dynamic programming, starting from my very first struggles and working up to the techniques I use today. In this first blog, I’ll talk about my personal experience with DP and the lessons I’ve picked up along the way.
I still remember when I first started leetcoding during my undergrad. It was a time when I was trying to solve as many problems as possible, just to get better at coding. I had recently switched to LeetCode, and that’s when I was exposed to all sorts of problem patterns. It was overwhelming, and honestly, it still is sometimes. However, one concept that always seemed especially confusing to me was dynamic programming (DP).
Just the name itself sounded strange to me. What does "dynamic" even mean here? Aren’t all the functions already dynamic when we pass arguments? That was my first thought, completely clueless. I had no idea how wrong I was.
At that time, I didn’t have much time to dive deep into DP. I was in my 2nd year, juggling a ton of things, and I was more focused on solving as many problems as possible rather than really understanding the concepts behind them (big mistake!). I managed to get placed pretty early in my placement process, so I can't complain too much about that strategy. But now, after solving a lot more problems, I realize how important it is to truly understand dynamic programming. So, I thought I’d take the chance to reflect on my journey with DP and share whatever I’ve learned. And that’s what this series is all about.
The First Taste of DP: A Very Rough Start
I’ll be honest, my first experience with DP was frustrating. I tried solving simple problems like the Fibonacci sequence and felt completely lost. It felt like I was trying to climb a mountain with no map, and every time I thought I had figured it out, I’d realize I was solving the same sub-problems over and over. I had no idea about memoization, which is one of the key ideas in DP. Storing intermediate results was such a new and confusing idea to me.
At first, I just wanted to solve the problem directly and move on. I didn’t see the point in adding all this extra complexity. But over time, I started to understand that the whole point of DP is to save time by solving smaller pieces of a problem once and reusing them later. This concept didn’t click right away, but eventually, it did.
The Mistakes I Made and the Lessons I Learned
There were many moments when I thought I understood DP, only to get stuck on new problems that felt completely different from the ones I had solved before. One of the hardest problems for me was the knapsack problem. I thought I had it all figured out, but after hours of trial and error, I realized I was approaching it all wrong. I missed one of the most important concepts of DP: breaking problems down into smaller, simpler subproblems. That was a game-changer for me.
Another mistake I made early on was sticking with memoization (top-down recursion) and ignoring tabulation (bottom-up iteration). I thought memoization was the easier approach, but as I practiced more, I learned that tabulation is often more efficient, especially when recursion isn’t necessary. Understanding when to use one or the other took time, but it was an important lesson.
Perhaps the biggest lesson I learned was how important it is to really break down the problem before diving into a solution. I used to just skim through the problem and jump straight to coding, but that led to missed edge cases and hours of debugging. Now, I always spend time understanding the problem first, and it makes a huge difference.
Why DP Is Worth the Struggle
Looking back at my journey with DP, I can honestly say that the struggles were worth it. The power of DP is in its ability to break down complex problems into smaller, manageable pieces. It's like putting together a puzzle, you don’t just randomly try to force pieces together, you start to recognize patterns and figure out how they fit.
As I continued solving more problems, I started to notice patterns that helped me solve new problems more efficiently. Whether it was finding the minimum path in a grid, working with the longest increasing subsequences, or solving the famous coin change problem, I started to recognize the same techniques showing up again and again. It’s not about memorizing solutions, it’s about spotting the patterns and applying them to different problems.
Conclusion: Embracing the Journey
I know I’m far from mastering DP, but every problem I solve teaches me something new. Even though I’ve solved a lot of problems, I always find myself learning more with each new challenge. That’s what makes DP exciting, it’s like a puzzle that keeps changing, and you always find something new to learn.
This is just the first part of my journey with dynamic programming. In the next blog, I’ll dive into some common patterns that have helped me understand DP better and solve problems more efficiently. Stay tuned for more!