Dynamic Programming

There is an ordering on the subproblems, and a relation that shows how to solve a subproblem given the answer to "smaller" subproblems, that is, subproblems that appear earlier in the ordering.

解釋之，就是一個問題可以細分為許多小問題，而這些分解下去的小問題之間又有順序上的關係，使得小問題的答案可以成為大問題答案的基石。

一般來說，我們會以陣列的形式來依序儲存小問題的答案，以供後續大問題解答時使用。

經典問題包含：
背包問題 (knapsack)
最長遞增序列 (Longest increasing subsequences)


[Reference]
Chapter 6 DP, from "Algorithms"
by S. Dasgupta, C.H.Papadimitriou, and U.V. Vazirani