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)