1582 articles
LC 198 House Robber asks you to maximize stolen money without robbing adjacent houses. The recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) is the canonical skip-one DP pattern asked at Amazon, Google, and Microsoft. Master the derivation, the three-phase DP evolution, and the O(1) space solution.
LC 213 House Robber II extends House Robber to a circular arrangement where the first and last houses are adjacent. The elegant solution runs the linear House Robber DP twice — once excluding the first house, once excluding the last — and returns the maximum. A top FAANG interview problem that tests systematic problem decomposition.
LC 740 Delete and Earn looks like a game problem but reduces to House Robber DP after a preprocessing step. Choosing value v earns v * count(v) points and forces deletion of v-1 and v+1, exactly the skip-adjacent constraint. Asked at Amazon and Meta to test whether candidates see through surface-level descriptions to the underlying DP pattern.
LC 53 Maximum Subarray is the foundational problem behind Kadane's Algorithm — a deceptively simple O(n) DP that asks: at each position, should I extend the current subarray or start fresh? Asked at Amazon, Google, and Microsoft and the basis for Maximum Product Subarray and other contiguous-subarray problems.
LC 152 Maximum Product Subarray extends Kadane's Algorithm by tracking both the running maximum and minimum products simultaneously. A negative number flips today's minimum into tomorrow's maximum. This dual-tracking insight is tested at Amazon, Google, and LinkedIn as a harder follow-up to Maximum Subarray.