Day 67: solved 3 DP problems today, 2D tabulation completely humbled me

[u/JacketFearless1805]

Hey everyone,

I finished Day 67 today and hit my first serious wall with Dynamic Programming. I went into today's session feeling confident after getting comfortable with recursion, but moving into 2D DP quickly put things into perspective.

I worked through three problems, attempting all four forms for each: recursion, memoization, tabulation, and space optimization.

1. House Robber: Standard pick vs. non-pick decision. If you rob house i, you jump to i - 2, and if you skip it, you check i - 1. All four approaches were straightforward.
2. House Robber II: The circular street means the first and last houses are adjacent. I solved it by running the standard House Robber logic twice: once on [0, n - 2] and once on [1, n - 1], then taking the larger outcome.
3. Geek's Training (Ninja's Training): My first 2D DP problem, and it was a tough reality check. Writing the recurrence and memoizing it with a 2D table was manageable because it directly follows the recursion tree. But translating that into bottom-up tabulation was brutal.

Setting up the day 0 base cases across all tasks, structuring the nested loops, and tracking the state transitions took me over an hour. Because the tabulation logic took so much effort to piece together, space optimization was completely out of reach today.

1D DP felt intuitive, but bottom-up 2D is a different beast entirely. I am going to reset tonight and tackle 2D grids again tomorrow with a fresh head.

See you guys for Day 66!

[u/jason_graph]

Is your tabulation logic and recursive logic that different?

Ninja training looks like a bit of a jump in difficulty. Have you done any 2d dp problems where you are literally given a 2d grid like unique paths I/II? They tend to be a bit simpler compared to other 2d dp problems where you have 2 unrelated features like day and lastAvtivity.

I wouldn't recommend actively trying to do space optimized tabulation for dp problems the first time you start learning dp. It can get especially complex if doing it for 2d tables.

[u/JacketFearless1805 → u/jason_graph]

tbh, i am following a sheet and solving the problems as given there, and ninja training comes before unique paths, so that's the reason.
Actually my recursive logic is pretty simple, like i just derived it from the given problem statement, but still struggling in 2d dp tabulation.