AdvancedDynamic Programming
Dynamic programming starts with one sentence
Before any code, finish this sentence: “dp[i] is …”. The recurrence, base cases and loop order follow from it.
The idea
DP solves a problem by reusing answers to smaller versions of it. The hard part is choosing what “smaller version” means. Write it as a sentence: “dp[i] = the most money I can rob from the first i houses.”
Then ask how dp[i] relates to earlier entries (the recurrence), what the smallest cases are, and fill the table in an order where everything you need is already computed.
Worked example
House Robber: [2, 7, 9, 3, 1]
- dp[i] = best total using houses 0..i.
- At house i: skip it (dp[i−1]) or rob it (dp[i−2] + value). dp[i] = max of the two.
- dp: 2, 7, 11, 11, 12 → answer 12 (2 + 9 + 1).
In code (Python)
def rob(nums):
if not nums:
return 0
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
rob_it = nums[i] + (dp[i - 2] if i >= 2 else 0)
dp[i] = max(dp[i - 1], rob_it)
return dp[-1]O(n) time, O(n) space (O(1) with the next tip).
How to spot it
- “number of ways”, “minimum cost”, “maximum”, choices at each step that affect later ones.
Common mistakes
- Coding before you can say what dp[i] means.
- Getting the base cases wrong for i = 0 and i = 1.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →