The answer for i depends on a few earlier answers: memoize or tabulate.
Reach for it when
Count ways / minimum cost / maximum value over a sequence
Choices at each step that overlap (take or skip)
Brute-force recursion recomputes the same subproblems
Core idea
Define dp[i] in one sentence (for example, 'max money robbing houses 0..i'), write the recurrence from the last decision, and set base cases. When dp[i] only depends on the previous one or two entries, keep just those variables for O(1) space.
Template · O(n) time, O(1) to O(n) space
defrob(nums):
prev2 = prev1 =0# dp[i-2], dp[i-1]
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x) # skip vs take
return prev1
introb(constvector<int>&nums) {
int prev2 =0, prev1 =0; // dp[i-2], dp[i-1]
for (int x : nums) {
int cur =max(prev1, prev2 + x); // skip vs take
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
Common pitfalls
Not writing down what dp[i] means before coding
Wrong base cases (empty prefix, index 0)
Circular inputs: solve twice, excluding the first or the last element