# Dynamic Programming - Thief Variation Probem

I've encountered a Dynamic Programming problem which is a variation of the thief one.

Say you are a thief and you are given a number of houses in a row you should rob :

$$House_1,House_2 \dots House_N$$

with each house having the following values : $$(x_i \geq y_i \geq z_i \gt0)$$

You profit X if you rob a house but none of the adjacent houses.

You profit Y if you rob a house and exactly one of the adjacent houses.

You profit Z if you rob a house and both of the adjacent houses.

Cases with houses A-B-C would be :

$$Profit(001)=0+0+C_x$$ $$Profit(101)=A_x+0+C_x$$ $$Profit(110)=A_y+B_y+0$$ $$Profit(111)=A_y+B_z+C_y$$

Where 1 stands for robbing the house and 0 for not robbing the house

Obviously you can't utilize the Z value for the first and the last house and each set of values is random.

Now the question is : Which houses should you rob to get the maximum profit?

My main issue is that i can't establish a base case for this problem.

At first i thought of creating a N*M array with M being the maximum amount of houses i can rob from 0-N when every house is not robbed and think like : Rob it - Don't rob it but came up with nothing.

Any tips or directions would be appreciated.

For $$i=1,\dots,N$$, and $$r \in \{S,R,B\}$$ define $$OPT[i,r]$$ as the maximum profit that can be obtained by robbing a suitable subset of the first $$i$$ houses with the following constraints:
• If $$x=S$$ (as in Skip) then house $$i$$ must not be robbed.
• If $$x=R$$ then house $$i$$ must be Robbed while house $$i+1$$ will not be robbed (to avoid a case distinction later we pretend that house $$i+1$$ exists even when $$i=N$$).
• If $$x=B$$ then Both house $$i$$ and house $$i+1$$ need to be robbed.
For $$i=1$$ you have $$OPT[1,S] = 0$$, $$OPT[1,R] = x_1$$, $$OPT[1,B] = y_1$$.
For $$i>1$$ you have: $$OPT[i, S] = \max\{ OPT[i-1, S], OPT[i-1, R] \},$$ $$OPT[i, R] = \max\{ x_i + OPT[i-1, S], y_i + OPT[i-1, B] \},$$ $$OPT[i, B] = \max\{ y_i + OPT[i-1, S], z_i + OPT[i-1, B] \}.$$
The optimal profit is then: $$\max\{OPT[N, S], OPT[N, R] \}$$ and can be computed in $$O(N)$$ overall time using the above formulas.