In a city, the rents of apartments change every month according to the demand. If there are x apartments in the city, all the rents for 12 months are given for each apartment and also x one time relocation prices are given(Applies when you move from one apartment to other in the first month).
If a person comes to this city and wants to rent an apartment, optimize the rental cost for whole year by generating a month wise plan on where he must stay each month?
Can be solved by DP in O(x*x*m) where m is the number of months and x is the number of houses.