# Adjacent house , dynamic programming problem

I have to be honest this is a homework problem, but I just need to discuss this with some one. The problem is there is a row of n houses, with different profit e.g profit1 for house 1, it can be either positive or negative value. But the aim is to maximize the profit by buying a subset of these houses. So infact, you should buy houses which are >0 value. However, you cannot buy houses that adjacent to the house you are buying, e.g i-1 and i+1 should not be bought. I am not quite sure where to start to look at this problem, I mean what exactly will be the difference of looking it from the greedy or dynamic programing way. Thanks for any suggestion.

• Will the greedy algorithm work if the houses have profit (2,4,3) in that order? – Peter Shor Oct 25 '12 at 0:29
• The greedy algorithm will not work because it will aim for 4, which is the highest one, and then drop the ones besides it. – user1675999 Oct 25 '12 at 23:00

I'll just leave a broad hint. Suppose $H(1:n)=[h_1,h_2\ldots,h_n]$ is the list of houses. Suppose that we already know the set of houses to buy for the subarray $H(1:n-1)$. This solution either includes $h_{n-1}$ in its optimal list, or it doesn't. If it does include $h_{n-1}$, then we can't add $h_n$ to the list and we are done. If it doesn't include $h_{n-1}$, then we can check if the profit rises or drops with the inclusion of $h_{n}$.
Update:@user: Sorry, I forgot that there are negative values! You do need a 2D array and split the problem into to the small pieces $[h_i \ldots h_j]$ for $1\leq i < j\leq n$,