Section outline

  • This unit presents a motivating example, defines the problem and proposes a naive solution for it. The drawbacks of the naive solution are unravelled and some observations trace the route to a recursive algorithm based on dynamic programming. This algorithm is then reduced to a fully iterative solution. The asymptotic complexity of this last version is revealed.