Suppose that you run a simple consulting business. Your clients are mostly clustered on the East and West coasts. From month to month, you could either run your business from an office in NYC or an office in San Francisco. You have some budget numbers to help: if you run your business out of NYC in month i, you expect to incur costs N_i, and likewise costs S_i for San Francisco. Furthermore, every time you move from one office to another, you incur a moving cost, M.

Given monthly cost estimates N_i, S_i, for i=1 ... n, and the moving cost M,
Find the best schedule of where to work each month.
For example, suppose that M = 10, and
i=1 i=2 i=3 i=4
N_i 1 3 20 30
S_i 50 20 2 4then the optimal schedule is [NY, NY, SF, SF].
Write an algorithm (based on dynamic programming) to solve this problem.
Write the program using C++