动态规划

[waker0086]

参考资料

leetcode动态规划精讲 https://leetcode.cn/leetbook/detail/dynamic-programming-1-plus/

[waker0086]

回顾线性规划

https://blog.csdn.net/qq_29831163/article/details/88893234

[waker0086]

概念区分：动态规划与静态规划、递归、分治、回溯

https://zhuanlan.zhihu.com/p/256310842

• 线性规划是一类问题。
• 动态规划是一种算法或是一种分析手段

线性规划：目标函数为特定变量的线性函数，约束是这些变量的线性不等式（standard form）或等式（slack form），目的是求目标函数的最大值或最小值。线性规划和非线性规划在某些地方被称作静态规划

动态规划（英语：Dynamic programming，DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

示例

我们来举个线性规划例子：

小明的妈妈给了小明10块零花钱，小明拿着零花钱去买糖。糖果店有巧克力、奶糖和水果糖，分别是3块、2块、1块。小明每种糖都能尝尝的条件下，怎么卖数量最多的糖。

这个问题实在是很容易，先挨个买一颗，然后all in 最便宜的水果糖，得到结果一共是7颗（1，1，5）。

但是我们还是仔细看一下这个问题，通过确定规划目标和约束得到了以下不等式组：

但是我们突然想到，买糖不是可以一颗一颗的卖么。如果是一颗一颗卖，阶段其实就是产生了。花10块钱买到最多的糖的阶段来源于上一个阶段，在上一个状态的时候，小明需要决定花多少钱买一颗糖从而进化到最终的最佳状态。在这个过程里，小明手上的糖的数量就代表着阶段的数量，而原本的线性规划的问题就转化成了一个动态规划的问题。

[waker0086]

DP经典问题：背包问题

1. 参考：https://zhuanlan.zhihu.com/p/93857890
2. 【经典、系统】背包9讲 ：https://github.com/tianyicui/pack /【pdf】https://github.com/tianyicui/pack/raw/master/V2.pdf
3. 背包九讲——全篇详细理解与代码实现：https://blog.csdn.net/na_beginning/article/details/62884939