Blog

DP clicked

Two days, six problems, one realization that changed how I see dynamic programming.

I’ll be honest — I was nervous about DP. Not the same fear I had with binary search, something different. Binary search felt like a wall I couldn’t climb. DP felt like a room I’d been in before but couldn’t quite remember the layout of.

I’ve done these problems. Frog Jump, House Robber, Knapsack — I’ve seen all of them. And yet when I sat down on day 6, my first attempt at Frog Jump was this sad little function that just looked at the next two steps and returned a cost, with zero recursion, zero memoization, no dp array. Completely wrong.

That was humbling. But it was also useful.

DP clicked

Frog Jump — where it started coming back

After that broken first attempt I stepped back and thought about what DP actually is. You have choices at every step. Each choice has a cost. You want the minimum total cost. And crucially — you’re going to encounter the same subproblems repeatedly, so you store results instead of recomputing them.

Once I framed it that way, the recursive solution came out clean. From there, tabulation was mechanical — flip the direction, fill a table bottom-up. Space optimization came after: if you only ever look back two steps, you only need two variables.

Frog Jump — the three forms

Recursion + memoization: define the problem top-down, cache results in a dp array initialized to -1. Tabulation: fill from base case upward. Space optimization: since we only look at i+1 and i+2, two variables replace the entire array. Each form is the same logic, different shape.

House Robber II — circular array variant

Can’t rob the first and last house together. Solution: run the problem twice — once excluding the last house, once excluding the first. Take the max of both. The recursive DP came together after some debugging. Tabulation needed AI help on one edge case — when i+2 doesn’t exist, the pick case needs to handle it explicitly.

Ninja’s Training — first 2D DP

DP clicked

Three activities per day, can’t repeat the previous day’s activity. The dp state becomes dp[day][last activity]. Recursive version was manageable. Tabulation has more moving parts — you’re filling a 2D table and tracking which activity was last done. This one took AI help and I’m flagging it for revision.

Grid problems and the moment something clicked

Day 7 started with Ninja’s Training tabulation, which landed properly with fresh eyes. Then grid problems — and somewhere in here something shifted.

Grid Unique Paths

Move only right or down, count paths from top-left to bottom-right. Classic 2D DP. Recursion and tabulation came easily since I’d seen it before. Space optimization — using a single row and updating in place — took a moment to see clearly.

Minimum Path Sum

Same grid structure, now minimize the sum along the path. Solved cleanly from recursion all the way to space optimization without getting stuck. Starting to feel the rhythm.

Minimum Falling Path Sum — variable start and end

This one matters more than it looks. Previous grid problems had a fixed start and fixed end. Here both are variable — start anywhere in the first row, end anywhere in the last. That changes how you initialize and how you read the final answer. Worth revising once more before the contest.

Subset Sum equals K

First DP on arrays with a decision at each element — include it or skip it. Solved the recursive + memoization version without any help. Then jumped straight to 1D space optimization, skipping the full 2D tabulation. It worked. The dp array here is of size k+1, representing whether each sum is achievable.

0/1 Knapsack

The classic. Two choices per item: take it or leave it. Recursive and tabulation done. The single-array optimization — using one array instead of two and iterating backwards to avoid overwriting — is the one thing still slightly fuzzy. Coming back to it.

The insight that changed everything

“It’s just about knowing the recursion really well.”

Once the recursive structure is clear — what the choices are, what the base cases are, what you’re minimizing or maximizing — tabulation is just that same logic written bottom-up. Space optimization is just noticing what rows or columns you actually need. You’re not learning three different things. You’re learning one thing in three different forms.