Two Pointer Problems (Part 2) - Sliding Window
Two pointers are used to scan in two directions during traversal, achieving the desired algorithmic goals.
Core Idea of Dynamic Programming
The core idea of dynamic programming lies in breaking down a problem into smaller subproblems and retaining previously computed results to reduce computational complexity.
Let’s illustrate with an example:
A: 1+1+1+1+1+1+1+1 = ?
B (calculating): 8
A: What if we add “1+” to the left side of the equation?
B (quickly): 9
A: How did you arrive at the answer so quickly?
B: Just add 1 to 8.
A: So you didn’t have to recalculate because you remembered the value of the first equation as 8. Dynamic programming algorithms also memorize previously computed solutions to save time.
198. House Robber
- When there is only one house, we choose to rob it.
- When there are two houses, we choose the one with the larger amount to rob.
- If there are more than two houses, for example, the third one, we need to consider whether the sum of the first and third houses is greater than the second one. If the sum of the first and third houses is greater, we rob both the first and third houses; otherwise, we skip the first and third houses and rob the second one.
- Generalizing to the common case, for the first i houses, we have two options for robbing:
- Robbing the ith house, which results in the total amount being the value of the ith house plus the total amount of money robbed from the first i-2 houses.
- Not robbing the ith house, resulting in the total amount being the same as the total amount robbed from the first i-1 houses.
We always choose the option that yields a higher amount between 1 and 2. Here, we use
