#
4.1. Dynamic Programming: Overview
In
- NOW
- Divide-and-Conquer Method
- Dynamic Programming Method
- Greedy Method
- Backtracking Method
- Local Search Method
- Branch-and-Bound Method
- Etc.
- From Wikipedia: Dynamic programming is both a
- mathematical optimization method and
- a computer programming method.
- A complicated problem is broken down into simpler sub-problems in a recursive manner.
- Overlapping subproblems
- A problem is broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.
- Optimal substructure
- A solution to a given optimization problem can be constructed efficiently from optimal solutions of its subproblems.
- When applicable, the method takes far less time than other methods that don't take advantage of the subproblem overlap like the divide- and-conquer technique.