You want to travel by bus, from city C1 to city Cn. Cities C2 to Cn-1 inclusively are on the road between C1 and Cn (e.g., if going from Saint John to Halifax, you would also go through Sussex, Moncton, Amherst, and Truro). There are bus rides between each pair of cities, with a different price associated with each bus ride, and it might be cheaper to make one (or more) stops than take the direct ride between C1 and Cn (e.g., it may cost $100 for the ride between Saint John and Halifax non-stop, but it may cost $30 for Saint John to Moncton and then $50 from Moncton to Halifax). The problem is to find the set of bus rides (or the set of cities where to stop) that will make you travel from C1 to Cn at the cheapest total cost. There is a constraint that you can't change the bus more than twice during the whole trip (max 2 intermediate stops). Give a dynamic programming algorithm for this (just formula is OK). Also explain how you would find out which cities exactly are to become our stops (not only what the cheapest overall cost is).