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.

Thanks in advance.