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.