实战
新的硬币找零问题。假设我们有⼏种不同币值的硬币<br>v1，v2，……，vn（单位是元）。如果我们要⽀付w元，求最少需要多少个硬币。⽐如，我们有3种不同的硬币，1元、3元、<br>5元，我们要⽀付9元，最少需要3个硬币（3个3元的硬币）。
0/1 背包问题
如何量化两个字符串的相似度？
如何编程计算莱⽂斯坦距离？
如何编程计算最⻓公共⼦串⻓度？<br>
我们有⼀个数字序列包含n个不同的数字，如何求出这个序列中的最⻓递增⼦序列⻓度？⽐如2, 9, 3, 6, 5, 1, 7这样⼀组数字序<br>列，它的最⻓递增⼦序列就是2, 3, 5, 7，所以最⻓递增⼦序列的⻓度是4。
0-1背包问题升级版
淘宝的“双⼗⼀”购物节有各种促销活动，⽐如“满200元减50元”。假设你⼥朋友的购物⻋中有n个（n>100）想买的商品，她希望从⾥⾯选⼏个，在凑够满减条件的前提下，让选出来的商品价格总和最⼤程度地接近满减条件（200元），这样就可以极⼤限度地“薅⽺⽑”。
理论 ⼀个模型三个特征
什么是“⼀个模型”？它指的是动态规划适合解决的问题的模型。我把这个模型定义为“多阶段决策最优解模<br>型”。
1.最优⼦结构<br>最优⼦结构指的是，问题的最优解包含⼦问题的最优解。反过来说就是，我们可以通过⼦问题的最优解，推导出问题的最优<br>解。如果我们把最优⼦结构，对应到我们前⾯定义的动态规划问题模型上，那我们也可以理解为，后⾯阶段的状态可以通过前<br>⾯阶段的状态推导出来。
2.⽆后效性<br>⽆后效性有两层含义，第⼀层含义是，在推导后⾯阶段的状态的时候，我们只关⼼前⾯阶段的状态值，不关⼼这个状态是怎么<br>⼀步⼀步推导出来的。第⼆层含义是，某阶段状态⼀旦确定，就不受之后阶段的决策影响。⽆后效性是⼀个⾮常“宽松”的要<br>求。只要满⾜前⾯提到的动态规划问题模型，其实基本上都会满⾜⽆后效性。
3.重复⼦问题<br>这个概念⽐较好理解。前⾯⼀节，我已经多次提过。如果⽤⼀句话概括⼀下，那就是，不同的决策序列，到达某个相同的阶段<br>时，可能会产⽣重复的状态。
