Dynamic Programming

Compare to Greedy and Divide_and_conquer

Greedy. Build up a solution incrementally, myopically optimizing some local criterion.

Divide-and-conquer. Break up a problem into sub-problem into sub-problems, solve each sub-problem independently, and combine solutions to sub-problems to form solution to original problem.

Dynamic programming. Break up a problem into a series of overlapping sub-problems, and build up solutions to larger and larger sub-problem.

Dynamic programming hallmark

Optimal substructure An optimal solution to a problem(instance) contains optimal solutions to subproblems.

Overlapping subproblems A recursive solution contains a “small” number of distinct subproblems repeated many times.

Example:Weighted Interval Scheduling

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

Memoization是常常和动态规划搭配使用的解决重复计算问题的放法，其原理是自底向上计算值，并储存起来，需要用到的时候直接取存储的值，而不是像递归那样重新计算。

在这里插入图片描述

在这里插入图片描述

下面就是我说的自底向上的例子：

在这里插入图片描述