动态规划算法

动态规划算法的核心思想是记住已经求过的解，记住求解的方式有两种：1、自顶向下备忘录法 2、自底向上

自上而下：从最顶端开始不断地分解问题，直到你看到问题已经分解到最小并已得到解决，之后只用返回保存的答案即可。这叫做记忆存储；

自下而上：直接开始解决较小的子问题，从而获得最好的解决方案。在此过程中，你需要保证在解决问题之前先解决子问题。这可以称为表格填充算法。

自下而上用到了迭代技术，而自上而下则用到了递归技术。

动态规划原理

1、最优子结构：用动态规划求解最优化问题的第一步就是刻画最优解的结构，如果一个问题的解结构包含其子问题的最优解，就称此问题具有最优子结构性质。因此，某个问题是否适合应用动态规划算法，它是否具有最优子结构性质是一个很好的线索。使用动态规划算法时，用子问题的最优解来构造原问题的最优解。因此必须考查最优解中用到的所有子问题。

2、在斐波拉契数列和钢条切割结构图中，可以看到大量的重叠子问题，比如说在求fib（6）的时候，fib（2）被调用了5次，在求cut（4）的时候cut（0）被调用了4次。如果使用递归算法的时候会反复的求解相同的子问题，不停的调用函数，而不是生成新的子问题。如果递归算法反复求解相同的子问题，就称为具有重叠子问题（overlapping subproblems）性质。在动态规划算法中使用数组来保存子问题的解，这样子问题多次求解的时候可以直接查表不用调用函数递归。

动态规划的经典模型

1.线性模型

最经典的问题就是斐波那楔数列的问题，每个数的值都是一个状态，可以用F[i]表示表示第i个数的值是多少。每个数都是由F[i-1]+F[i-2]转移而来。

另外一个经典的问题就是最长上升自序列（LIS），有一串序列，要求找出它的一串子序列，这串子序列可以不连续，但必须满足它是严格的单调递増的且为最长的。把这个长度输出。示例：1 7 3 5 9 4 8 结果为4。

我们非常容易表示他的状态，我们用f[i]表示以第i个数结尾的，最大的上升自序列是多少？那么它是怎么转移的呢？非常容易想到肯定是从左边的的数转移而来，能转移的数满足什么条件呢？肯定是比a[i]更小的。

线性模式还可以拓展成二维问题，例如背包问题，用f[i][j]表示前i个物品，凑成大小为j的背包，最大的价值是多少。

这类问题非常的多，但是思路都是这样，无非就是从左往右，从上到下，从低维到高维进行转移。

2.区间模型

对于每个问题，都是由子区间推导过来的，我们称之为区间模型，下面是一个例子。

我们有一个连续的序列，每个序列上面都是一个数字c[i]，每次我们都能够消灭一个连续的回文子序列，消灭之后左右会合并，成为一个新序列，问最少需要多少次才能够把整个序列消灭掉。回文就是从左到有从右到左读到的序列都是一样的。题目比较抽象，我们通过一些例子来说明这个问题吧？例如一开始的序列是1 4 4 2 3 2 1，那么我们最少需要2次，先消灭掉4 4 ， 然后再消灭调1 2 3 2 1.第二个例子是 1 2 3 4 5 5 3 1，我们先消灭掉2 然后再消灭掉4， 最后消灭 1 3 5 5 3 1， 需要3次。

我们经常用f[i][j]来表示消灭i,j区间需要的代价，文末有链接详细叙述这个问题，大家感兴趣的可以看一看。

3.树状模型

我们在数据结构树上面进行最求最优解、最大值等问题，上述我们讲的这个绩效考核就是一个树状模型，具体不再累叙。