What?

Similar to Greedy Algorithms, it’s a methodology for solving optimisation problems. It involves:

  • Breaking the problem into subproblems that (ideally) repeat several times in the larger problem.
    • Each problem is ordered from smallest to largest.
  • Designing the optimal solution so that it’s (ideally) repeatedly constructed from the optimal solutions of the subproblems.
    • The optimal solution of the subproblems can be constructed from the optimal solutions of the sub-sub-problems. (Optimal Substructure)
  • Storing the Subproblem solutions: (Memoization)