← Quiz: 1D Dynamic Programming Patterns: all 10 questions
Quiz: 1D Dynamic Programming Patterns · Question 3 of 10
In house robber, why is dp[i] = max(dp[i − 1], dp[i − 2] + money[i])?
In house robber, why is dp[i] = max(dp[i − 1], dp[i − 2] + money[i])?
- A.Because we must rob every second house
- B.Either house i is skipped (best up to i − 1), or it is robbed and house i − 1 must be skipped
- C.Because money[i] is always the largest
- D.Because the houses are sorted
Answer & explanation
Correct answer: Either house i is skipped (best up to i − 1), or it is robbed and house i − 1 must be skipped
The two cases cover every legal plan, and we keep the better one.
Can you get the rest right without peeking?
Take the timed Quiz: 1D Dynamic Programming Patterns quiz free. Pass it to earn XP and count towards your certificate.
Start the quiz →