Can the House Robber problem be solved with a Sliding Window solution?

Question

I was reading an article on how to solve sliding window problems and it said:

3. Fast/Lagging This one is a little different, but essentially the slow pointer is simply referencing one or two indices behind the fast pointer and it’s keeping track of some choice you’ve made. In the House Robber problem you are trying to see what the maximum amount of gold you can steal from houses that are not next door to each other. Here the choice is whether or not you should steal from the current house, given that you could instead have stolen from the previous house.

So, I tried to solve the House Robber problem using a Sliding Window (fast/lagging) solution. It worked for a lot of test cases, but there were some that it just would not solve.

I came to the conclusion that it wasn't possible as the problem is recursive (you don't know whether to rob this house and next-door-but-one unless you know whether to rob next-door-but-one and next-door-but-one, unless you know whether... etc. etc.)

So, I clicked the Solution button on leetcode and the solutions presented were recursion and tabulation.

Is it possible to solve this problem using a 'sliding window'?

Answer 1

Yes you can! It's called dynamic programming, though.

Usually, the sliding window technique stores only information local to the window, but to make this work, you should store also the global solution up until the current window position.

What you store in a window (size 2?) is what the optimal solution is if you pick the last house of the window, and what is the optimal solution when you skip the last house of the window.

We call this technique dynamic programming, and not sliding window, although they have much in common.

P.S. this problem is also known as Independent Set in Path Graphs.

---

I don't know if you call this sliding window, but here is one way of solving it:

def window(data):
    if not data:
        return 0
    pick, skip = data[0], 0
    for window_idx in range(1, len(data)):
        pick, skip = data[window_idx] + skip, max(skip, pick)
    return max(pick, skip)


data = [14, 7, 11, 8, 13, 9, 10, 12]
print(window(data))  # 14 + 11 + 13 + 12 = 50