# Why Least Cost Airline Fare problem shows optimal substructure when given a certain intermediate stops?

As an example of a problem that is unlikely to exhibit optimal substructure, consider the problem of finding the cheapest airline ticket from Buenos Aires to Moscow. Even if that ticket involves stops in Miami and then London, we can't conclude that the cheapest ticket from Miami to Moscow stops in London, because the price at which an airline sells a multi-flight trip is usually not the sum of the prices at which it would sell the individual flights in the trip.

(Using online flight search, we will frequently find that the cheapest flight from airport A to airport B involves a single connection through airport C, but the cheapest flight from airport A to airport C involves a connection through some other airport D.) However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure: the cheapest flight from A to B involving a single connection is either the direct flight; or a flight from A to some destination C, plus the optimum direct flight from C to B.

It is very unclear that why optimal substructure can be observed when we specify the at most intermediate stops? From my understanding (which can be wrong), even if we provide the at most intermediate stops such as K = 4, we can not conclude that the cheapest price will be the sum of the prices of the individual flights in the trip as the multi flight trip is usually not the sum of the prices of the individual intermediate flights.

Can anyone please explain me with examples?

• Was my answer helpful? Have you considered upvoting and accepting my answer? Please comment if my answer can be improved. (This comment will be deleted upon feedback.) Commented May 11, 2022 at 18:27

However, if the problem takes the maximum number of layovers as a parameter, then the problem has optimal substructure. The cheapest flight from A to B that involves at most $$k$$ layovers is either the direct flight; or the cheapest flight from A to some location C that involves at most $$t$$ layover for some $$t$$ such that $$0\le t\le k-1$$, plus the cheapest flight from C to B that involves at most $$k-1-t$$ layovers.