Dynamic Programming

如果一个问题具有以下两个要素：

• 最优子结构(optimal substructure)
• 重叠子问题(overlap subproblem)

则可以用动态规划求最优解。

如何想到用用动规

1. One of the following three
   • a) Maximum/Minimum
   • b) Yes/No
   • c) Count(*)
2. Can not sort / swap

常见DP类型

1. Matrix DP (10%)
2. Sequence (40%)
3. Two Sequences DP (40%)
4. Backpack (10%)

DP四要素

1. 状态 State

   灵感，创造力，存储小规模问题的结果

2. 方程 Function

   状态之间的联系，怎么通过小的状态，来算大的状态

3. 初始化 Intialization

   最极限的小状态是什么, 起点

4. 答案 Answer

   最大的那个状态是什么，终点

Two Sequences Dp

state: f[i][j]代表了第一个sequence的前i个数字 /字符 配上第二个sequence的前j个...

function: f[i][j] = 研究第i个和第j个的匹配关系

intialize: $$f[i][0]$$ 和 $$f[0][i]$$

answer: f[s1.length()][s2.length()]