02
Take or skip (DP — 1D Linear Sub-pattern)
At each element choose: take it (and you may not take its neighbour) or skip it. dp[i] = max(dp[i − 1], dp[i − 2] + value[i]).
Signals in the problem statement
- ›
"no two adjacent"
- ›
"if you pick x you can't pick its neighbours"
- ›
"houses in a row / circle"
- ›
"delete x and earn x points, but x − 1 and x + 1 disappear"
What makes it different
The rule is a max of two choices, not a sum. If the "neighbours" are neighbours by value (Delete and Earn), first put the values into buckets so neighbours become neighbouring cells.
Questions
ordered from “learn the idea” to “recognise it without help”- 1House RobberWalkthroughMediumBasic Anchor·LeetCode #198
- 2House Robber IIWalkthroughMediumSlight Variation·LeetCode #213
- 3Delete and EarnWalkthroughMediumPattern Transfer·LeetCode #740
Template
take-skip-template.cpp
// Take or skip: the best total from a[0..i] where no two taken elements are neighbours.
// dp[i] = max(skip = dp[i - 1], take = dp[i - 2] + a[i]).
long long takeSkip(const vector<int>& a, int from, int to) { // inclusive range
long long prev2 = 0, prev1 = 0; // best up to i - 2, best up to i - 1
for (int i = from; i <= to; i++) {
long long cur = max(prev1, prev2 + a[i]);
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
// Circle: first and last can't both be taken.
// n == 1 ? a[0] : max(takeSkip(a, 0, n - 2), takeSkip(a, 1, n - 1))Remember this · DP — 1D Linear
Trigger
"Number of ways", "maximum/minimum up to i", choices at each step that depend on the previous one or two.
Think
If I knew the answer for every smaller prefix, how would I get the answer for i?
Key question
What does dp[i] mean in one sentence?