终于讲到动态规划了~该来的总会来的……
作为算法的一大核心，我大动态规划的影响力不可谓不大。很多工业级的算法里，都清晰可见动态规划的模样。 你问我为何这么普及？道理很简单。丫的动态规划也是一种思想！！！
相信刚开始学算法的同学都有过被贪心虐的死去活来的时候，那种策略的论证过程，有时明明就是只差一点点，但是就是做不出…… 如果你喜欢这种感觉，那么恭喜你，动态规划也是充斥着这种没着没落的感觉…… 如果你不喜欢~反正也上了算法这条贼船，多学点东西总是没坏处的~
动态规划思想
好了，不废话了。如果之前接触过贪心问题的话，对于问题的子问题化、分别求解和组合出最后结果的整个思想肯定不陌生。动态规划使用相同的思想，也是将待求解的问题分解为若干个子问题，按顺序求解子问题，同时前一子问题的解，为后一子问题的求解提供了有用的信息。
动态规划适用条件
既然说动态规划是一种思想，那么就要讨论下动态规划的成立条件。
如果第四条对于一个问题不成立，那么这个问题的计算方法就退回到了一般的回溯法或者搜索问题，如果这个时候仍然使用动态规划进行求解，整个问题的求解并不会得到任何优化。
动态规划一般步骤
动态规划描述子问题一般使用“状态”这个词，选定子问题的某种性质作为“状态”。整个问题从最初状态开始，然后按照某种决策顺序依次解出对应状态的最优解，最后到达结束状态。整个决策的顺序需要根据问题进行调整。
也就是说，动态规划的解题步骤可以一般性的划分为以下几种：
最重要的就是理解”状态“对于每个问题来说是哪一个性质。 一个子问题可能有多个状态，比如对于背包问题来说，子问题的性质就包括”当前重量“”当前体积“两个。但是单个子问题我们只能计算一个性质，也就是只能关注一个状态。
应用举例
额，先看个斐波那契数列的例子吧。 斐波那契数列的解法很多，，搜索和分治法都可以解出，但是可以看到的是，如果给定的N比较大，那么搜索和分治都会变得很慢，甚至有溢出的问题出现。关键就在于这两种方法都没有保存子问题的解，而是会重复进行很多计算。 一旦出现重复的子问题求解，优先考虑动态规划方式求解，一般都会获得很多优化。 斐波那契的动态规划解法：
OK。现在我们就可以开始计算了，
a[2] = a[1] + a[0];a[3] = a[2] + a[1];a[4] = a[3] + a[2];……a[n] = a[n-1] + a[n-2]
这样就可以显示出动态规划的优点所在：针对每一个状态只需要进行一次运算，之后就可以重复利用这个状态的值，从而减少了大量不必要的重复计算
版权声明：本文为博主原创文章，转载须注明地址：
世上没有绝望的处境，只有对处境绝望的人。
