Principle of optimality
= Principle of optimality
After fixing an initial decision in an optimal solution, the remaining decisions must solve the resulting residual problem optimally, with the relevant state and constraints retained. Otherwise substituting a better continuation would improve the original solution. This replacement argument justifies <dynamic programming recurrences> when the chosen <dynamic programming state> contains all information needed by future decisions.