Dynamic Programming (optimally plan processes)
Dynamic programming is a very powerful algorithmic paradigm in which a problem is solved by identifying a collection of subproblems and tackling them one by one, smallest first, using the answers to small problems to help figure out larger ones, until the whole lot of them is solved.
When solving a problem by dynamic programming, the most crucial question is, what are the subproblems?
The “base cases” of dynamic programming are the very smallest subproblems.
Every dynamic program has an underlying directed acyclic graphs (DAG) structure: think of each node as representing a subproblem, and each edge as a precedence constraint on the order in which the subproblems can be tackled. Having nodes U1, …, Uk point to V means “subproblem V can only be solved once the answers to U1, …, Uk are known”.
The reason why recursion works better with divide-and-conquer (DAC) than dynamic programming (DP) is that in DAC, a problem is expressed in terms of subproblems that are substantially smaller (half the size). In a typical DP formulation, a problem is reduced to subproblems that only slightly smaller. Efficiency is therefore obtained by explicitly enumerating the distinct subproblems and solving them in the right order.
The knapsack problem generalizes a wide variety of resource-constrained selection tasks. (replace “weight” for bag with “CPU time” or “bandwidth”)
To be continue…