I was reading an article on how to solve sliding window problems and it said:
- 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'?