动态规划Dynamic Programming
动态规划问题
问题特性
最优子结构 Optimal Substructure
子问题最优解 可以 得出 原问题最优解
重叠子问题 Overlapping Subproblems
递归过程中会出现重复的子问题求解
价值
一旦出现上述问题特征，可以使用 两大手法 瞬间降低时间复杂度
两大手法
Top Down 沿途记忆
沿途记忆中间的值，下次再求时，不再求
Bottom Up 反递归
先求 小问题，求大问题时，已有小问题的答案
时间复杂度分析
练习
切绳子问题Rod Cutting
已知一个价格列表
| 长度 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 价格 | 1 | 5 | 8 | 10 | 13 |
问，给你一个 n 米的绳子，怎么切，才值最多钱
最长公共子序列Longest Common Subsequence | LCS
已知两个字符串，找出他们最长的公共子字符串
比如
"ACTGGGTAC" "AGTTAC"
AGA 是 其中一个 Common Subsequence，因为
"ACTGGGTAC" ^ ^ ^ "AGTTAC" ^^ ^
AGTAC 是其中一个 LCS
