City staying problem.

There are two cities, City A and City B. Every day it costs a different amount to stay in either city. For instance, city A costs {a1, a2, ... an} to stay for days 1, 2, .., n. and city B costs {b1, b2, ,,, , bn} to stay for days 1, 2, ..., n. In addition, it takes a constant cost c to travel from city A to city B, and vice versa.

Describe an O(n) algorithm in that gives the least cost to stay for n days.

For example, lets stay n = 3; we are staying for 3 days. We could choose to stay at city A for days 1 and 2 (if the cost of a1 + a2 is less than b1 + b2), but then if the cost to stay in city A for day 3 (a3) is very high (greater than the cost of c + b3), we can travel to City B and stay there instead to minimize the cost. This looks like a dynamic programming problem to me.