动态规划常常适用于有重叠子问题和最优子结构性质的问题。
最优子结构性质 如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质。
无后效性 即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
子问题重叠性质 子问题重叠性质是指在用递归算法自顶向下对问题求解时，每次产生的子问题并不总是新问题。
通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：
一旦某个给定子问题的解已经算出，则将其存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
思路
通常我们从过程的最后一步开始考虑，而不是先考虑过程的开始。
找到任何一个规律后,把这个规律表示出来,未知的部分全部用代数解决
比如01背包问题对每一件商品无非两种情况, 要么装要么不装, 取两者的大者, 于是这里有一个是否装和max的逻辑,
写下来就是, 对于商品i而言, 最大价值为: max(装的情况的价值, 不装的情况的价值)
N为商品种类数量
F(i, m)表示重量为i的背包, 在有1-m种商品可供选择时能装的最大价值
W(i)表示商品i的重量, V(i)表示商品i的价值
状态转移方程即: F(k, m) = max(F(k - W(m), m - 1) + V(m), F(k, m - 1)), k - W(m) >= 0, 1 =< m =< N
给定体积的背包里, 对每一件商品而言有两种选择, 需要找出价值大的,
遍历完所有商品得到给定体积的背包的最大价值, 体积是一个额外限制, 所以比零钱问题多了一个维度
而找零问题是对每一个找零目标(如1分钱,2分钱,76分钱)有几种硬币可选, 需要找出硬币数量少的
题0 费波那契
使用计算机解决一个问题是在思考如何将这个问题表达成状态（用哪些变量存储哪些数据）以及如何在状态中转移（怎样根据一些变量计算出另一些变量）。
所以空间复杂度是为了支持计算所必需存储的状态有多少，时间复杂度是从初始状态到最终状态的过程中需要多少步
比如说计算第100个费波那契数，每一个费波那契数就是这个问题的一个状态，每求一个新数字只需要之前的两个状态。
所以同一个时刻，最多只需要保存两个状态，空间复杂度就是常数；每计算一个新状态所需要的时间也是常数且状态线性递增，所以时间复杂度也是线性的。
费波那契数这个问题里没有最的概念, 而"最"都是比出来的,
没有最就不用比了, 其实也没得比, 因为每一步的计算结果都只有一个值,
有些问题每一步有多种可能性, 往往就要选一个最好的
题1 用最少的硬币找零钱
给定N种硬币,它们的价值分别是(V1, V2, ..., VN)
求最少需要几枚硬币才能凑出价值S(每种硬币都是要多少有多少)
这里出现了一个最字, 有N种硬币, 意味着每阶段都要用N种硬币去尝试得到一个"最"优解, 即穷举N种硬币的情况并比较
这一点和费波那契很像, 都是从目标值1开始一步步算上去的
题2 求最长上升子序列的长度
如: 5，3，4，8，6，7
状态: 以第i个元素结尾的情况
LIS(i) = max{LIS(j) + 1} j < i and a[j] < a[i]
题3 二维地图摘苹果
F(1, 1) = A(1, 1)
F(1, 2) = F(1, 1) + A(1, 2)
F(2, 1) = F(1, 1) + A(2, 1)
F(i, j) = max(F(i - 1, j), F(i, j - 1)) + A(i, j)
N * M个子问题, 每个子问题两次判断, O(N * M * 2)
比之前的问题复杂的是, 这个问题是二维的, 有两个参数
题4 三趟摘苹果
给定一个M行N列的矩阵(M*N个格子)，每个格子中放着一定数量的苹果。
从左上角的格子开始，只能向下或向右走，目的地是右下角的格子。每走过一个格子，就把格子上的苹果都收集起来。
然后从右下角走回左上角的格子，每次只能向左或是向上走，同样的，走过一个格子就把里面的苹果都收集起来。
最后，再一次从左上角走到右下角，每过一个格子同样要收集起里面的苹果 (如果格子里的苹果数为0，就不用收集)。
求你最多能收集到多少苹果。
题目等价于三次都从左上角到右下角,
相当于三个人同时从左上角到右下角,
每步每人有向右和向下两种选择, 三个人即2*2*2有8种情况
三人位置的组合(如((5,5),(5,5),(5,5))表示三人都在右下角)能采到的苹果最大数为上一步所有可能位置的最大苹果数加当前位置的苹果数
递归向上直到左上角
每个位置的最大值计算出来后都保存
题5 考虑路费情况下的单源最短路径
有额外限制条件
寻路时有路费限制, 找最短路径
顶点i的过路费为S(i)
总经费为M
输出包括长度和所需费用,
对指定的结点(初始结点长度为0)和剩余金钱,
找出钱够的邻结点, 如果路能更短就更新那个结点的长度和剩余金钱, 也可以再记上来自当前结点(用于回溯路径),
处理完这个结点后, 找出长度最短的未处理的结点, 再进行上述处理, 直至没有未处理的结点
在dijikstra算法中加入剩余金钱这一参数后得到解法
时间空间复杂度也是原来的平方级
题6 01背包问题
有一个包和n个物品，包的容量为m，每个物品都有各自的体积和价值，
问当从这n个物品中选择多个物品放在包里而物品体积总数不超过包的容量m时，能够得到的最大价值是多少？
[对于每个物品不可以取多次，最多只能取一次，之所以叫做01背包，0表示不取，1表示取]
N为商品种类数量
F(i, m)表示重量为i的背包, 在有1-m种商品可供选择时能装的最大价值
W(i)表示商品i的重量, V(i)表示商品i的价值
状态转移方程即: F(k, m) = max(F(k - W(m), m - 1) + V(m), F(k, m - 1)), k - W(m) >= 0, 1 =< m =< N
心得
完全不存在具有后效性状态定义的问题都是贪心问题, 如求一个数组中的最大值
如果用组合方法求解, 就是把所有的情况都找出来, 然后取最值
但凡问题里含有最字,往往都可以这样穷举来求解, 但是往往时间复杂度比较高
更好的算法意味着可以省一些资源, 所以才说更好
动态规划的时间复杂度一般是:
O(不同的子问题个数 * 每个子问题的状态数)
Bellman是个数学家，DP里的programming不是编程的意思，而是决策。
但这种决策不是一下就出来的，而是一步步(multistage)积累出来。
换句话说我们需要一个决策，但这个决策太大了，我们做不了，所以需要把他递归到我们可以简单做出决策的状态，然后从这些状态开始，慢慢的"动态地"演进到最终的决策。
比如说用最少的硬币换零钱，突然和你说要换78分钱，你怎么就能迅速给出答案呢，你不能。但是如果是1分的话，你就可以，2分的话呢，就是在1分的基础上再加1分，你也可以。
于是你就慢慢地从1分开始一直算到78就有答案了。从另一个角度说，如果你用DP算出了怎么换78分，那如果我问你76分怎么换，你也应该有答案了。
每个阶段只有一个状态->递推；费波那契数
每个阶段的最优状态都是由上一个阶段的最优状态得到的->贪心；计算数组最大值
每个阶段的最优状态是由之前所有阶段的状态的组合得到的->搜索；Dijkstra寻路
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的->动态规划。用最少的硬币换零钱
总的来说还是有些运算和(或)存储可以省, 好的算法也就是好在这里, 运筹的本质就是要省
找到哪里可以省就是关键, 即找到重叠子问题
DP的关键是通过状态的合并减少计算量, 进行BFS，并对BFS中每个点保存最优状态，如果有不同的路径BFS到了同一个点，留最好的一条就行, dijikstra就是这样
由于所有计算机上可计算的问题的算法都可以转为图灵机模型，而图灵机是一种带无限存储的自动机模型，也就是说能在计算机上解决的问题基本都能转换成上面这种状态迁移图
自底向上动态规划需要确保按适当顺序计算函数值,以保证在我们需要值的时候可以直接取到
自顶向下动态规划使用递归,往往更自然,而且不需要所有子问题的解
参考链接
https://www.zhihu.com/question/23995189/answer/35429905
https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/
http://www.hawstein.com/posts/dp-novice-to-advanced.html