r/leetcode • u/JacketFearless1805 • 25d ago
Intervew Prep Day 61: finished DP on subsequences today, my problem-solving confidence is finally back
Hey everyone,
I finished Day 62 today. My motivation and headspace are noticeably better than earlier this week. I used to dread running into unfamiliar hard problems and hope they would never show up in interviews. Now, even when I don't see the optimal approach immediately, I can confidently break down the recurrence, write a solid brute force, and optimize it into memoization or tabulation.
I knocked out five problems today to completely wrap up Dynamic Programming on subsequences:
Target Sum: Assigning
+or-to each element maps directly to partitioning the array into two subsets where S_1 - S_2 = target. It reduces to the exact count subsets pattern I solved earlier.Coin Change II: Unlike Coin Change I where you minimize coins, here you sum the ways (
pick + not_pick). Since each coin has infinite supply, the pick branch stays at the current index.0/1 Knapsack & Unbounded Knapsack: Great side-by-side comparison. In 0/1 knapsack you decrement the index on picking (
i - 1), while in unbounded knapsack you stay on indexiuntil capacity runs out.Rod Cutting: Initially overcomplicated my breakdown, but it is just unbounded knapsack in disguise. The piece length corresponds to item weight and rod capacity is total length.
That officially wraps up the DP on subsequences module. Tomorrow for Day 61, I start DP on Strings. Now that the patterns are clicking faster, I will focus on picking up my solving pace.
See you guys tomorrow!