 Solution

Dynamic programming solves overlapping subproblems once and stores their values for reuse. The principle of optimality says that the remaining decisions within an optimal solution must solve the corresponding residual subproblem optimally; otherwise replacing them by a better residual solution would improve the original one. Here removing one chosen stamp leaves an optimal way to form the remaining postage.