lets say now that you are planning to travel to a given city X over 10 days. For simplicity, this city has only 2 hotels, with prices varying each day (i.e., the price of one night may not be the same as the price on another night, but once the price for a particular night is fixed, it does not change later). You do not have much money, so you are willing to switch hotel when the price is better. The prices are given to you in 2 arrays:

H1P[i] = price of hotel 1 on day i H2P[i] = price of hotel 2 on day i

Since the hotels want to keep their clients, they both offer a rebate when staying consecutive nights: the first night is at the regular price, but the following nights (second, third, fourth, etc.) have a 10% rebate (i.e., regular price * 0.9). If you switch hotel and then come back, the first night back will be at regular price, and the other nights back will have the rebate (i.e., the rebate works only for consecutive nights). Provide a dynamic programming algorithm (formula only) to calculate the minimum cost you will have to pay for the 10 days. Hint: you will need 2 one-dimension arrays here...