动态规划算法的核心就是通过状态转移将原题转换为数个相似小问题。

初识动态规划：

动态规划的基本方法：递推

一个经典的例子: Fibonacci数列

Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。

求解Fn，需知道Fn-1，Fn-2，而求Fn-1又需要知道Fn-2，Fn-3，需要一步步递推至F1，F2
我们使用一个递归方法来实现该简单算法
当我们输入6时根据递推公式 Fn=Fn-1+Fn-2 即：
F(6)=F(5)+F(4)
=【F(4)+F(3)】+【F(3)+F(2)】=…

1
2
3
4
5
6
7
8
public int fibonacci(int n)
{
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    return fibonacci( n-1)+fibonacci(n-2);
}

假如我们输入的是6，那么我们执行的递归树如下：
avatar
显然在递归树中我们有多个节点被重复计算，例如F（2）被重复计算了5次，而且调用每一个函数的时候都要保留上下文，所以空间与时间上使用都极大，我们可以在计算过程中保存计算过节点的值，这样可以极大地节省时间和空间上的消耗。

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public static int Fibonacci(int n)
{
        if(n<=0)
            return n;
        int []Memo=new int[n+1];        
        for(int i=0;i<=n;i++)
            Memo[i]=-1;
        return fib(n, Memo);
    }
    public static int fib(int n,int []Memo)
    {
        if(Memo[n]!=-1)
            return Memo[n];
    //如果已经求出了fib（n）的值直接返回，否则将求出的值保存在Memo备忘录中。
        if(n<=2)
            Memo[n]=1;
        else Memo[n]=fib( n-1,Memo)+fib(n-2,Memo);  
        return Memo[n];
    }
````
- 创建了初始化一个n+1大小的Memo数组（默认值设为-1）来保存求出的斐波拉契数列中的每一个值
- 每次计算fib（n）前检查Memo数组中是否已存储了fib（n)计算的结果，若有直接返回fib（n）的值
- 如果没有计算后将值保存在fib（n）里面。
#### -状态和状态转移           
> 在介绍递推和记忆化搜索的时候，都会涉及到一个词---状态，它表示了解决某一问题的中间结果，这是一个比较抽象的概念

例题中的Fn，还是Fn-1，都是题目中n不同状态中Fn对应的不同状态，无论是递推还是记忆化搜索，首先要设计出合适的状态，然后通过状态的特征建立状态转移方程(Fn=Fn-1+Fn-2 )就是一个简单的状态转移方程）。
#### -最优化原理和最优子结构
> 在介如果问题的最优解包含的子问题的解也是最优的，就称该问题具有最有子结构，即满足最优化原理。

但这种用一个类似备忘录来存储计算过的结果的记忆化搜索还是利用了递归，上面算法不管怎样，计算fib（6）的时候最后还是要计算出fib（1），fib（2），而动态规划的核心，先计算子问题，再由子问题计算父问题。
所以不如直接由F1，F2 一步步逆推出Fn
```java
public static int fib(int n)
{
        if(n<=0)
            return n;
        int []Memo=new int[n+1];
        Memo[0]=0;
        Memo[1]=1;
        for(int i=2;i<=n;i++)
        {
            Memo[i]=Memo[i-1]+Memo[i-2];
        }       
        return Memo[n];
}

自底向上方法也是利用数组保存了先计算的值，为后面的调用服务。观察参与循环的只有 i，i-1 , i-2三项，因此该方法的空间可以进一步使用三个变量循环保留i，i-1 , i-2三项的值就好。这样从fib（1）到fib（n）只需要计算一次且遍历一次即可得出答案。
（本例其实并不能很好体现最优子结构，最长单调子序列有更好的体现）

- 决策和无后效性

一个状态演变到另一个状态，往往是通过“决策”来进行的。有了“决策”，就会有状态转移。而无后效性，就是一旦某个状态确定后，它之前的状态无法对它之后的状态产生“效应”（影响）。

即是说当你计算出Fn-2与Fn-1时，即便Fn-1 求值过程中需要Fn-3，但计算Fn的值时 Fn-3已不影响Fn的值。

动态规划模型：

1.线性模型

线性指的是状态的排布是呈线性的。

举例一个是经典的动态规划问题，被称为最长单调子序列。
 【例题】给定一个长度为n(1 <= n <= 1000)的整数序列a[i]，求它的一个子序列(子序列即在原序列任意位置删除0或多个元素后的序列)，满足如下条件：
  1、该序列单调递增；
  2、在所有满足条件1的序列中长度是最长的；

看到这种题目第一反应是直接dfs，把每一种情况枚举出来，但对于长度为n的数列长度没增加一个单位，子序列的数量是前者的指数级，我们可以尝试用动态规划，每次结果都在更短的情况下推出来，例如 可以在长度为n的序列基础上将长度n+1的序列的最长单调子序列推出来。假设第i个数取的情况下已经搜索出的最大长度记录在数组d中，即用d[i]表示当前搜索到的以a[i]结尾的最长单调子序列的长度，那么如果下次搜索得到的序列长度小于等于d[i]，就不必往下搜索了（因为即便继续往后枚举，能够得到的解必定不会比之前更长）；反之，则需要更新d[i]的值。最后d[d.lenght-1]即是整个数列的最长单调子序列的长度了。

avatar
如图，红色路径表示第一次搜索得到的一个最长子序列1、2、3、5，蓝色路径表示第二次搜索，当枚举第3个元素取的情况时，发现以第3个数结尾的最长长度d[3] = 3，比本次枚举的长度要大（本次枚举的长度为2），所以放弃往下枚举，大大减少了搜索的状态空间。
这时候，我们其实已经不经意间设计好了状态，就是上文中提到的那个d[i]数组，它表示的是以a[i]结尾的最长单调子序列的长度，那么对于任意的i，d[i] 一定等于 d[j] + 1 ( j < i )，而且还得满足 a[j] < a[i]。因为这里的d[i]表示的是最长长度，所以d[i]的表达式可以更加明确，即：

d[i] = max{ d[j] | j < i && a[j] < a[i] } + 1

这个表达式很好的阐释了最优化原理，其中d[j]作为d[i]的子问题，d[i]最长（优）当且仅当d[j]最长（优）。当然，这个方程就是这个问题的状态转移方程。状态总数量O(n), 每次转移需要用到前i项的结果，平摊下来也是O(n)的,所以该问题的时间复杂度是O(n^2)，然而它并不是求解这类问题的最优解，下文会提到最长单调子序列的O(nlogn)的优化算法。

接下来举例一个个人感觉可以很好将动态规划跟贪心区分开的一道例题（之前一直弄不清贪心与动态规划的区别）

    在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

一开始用贪心的想法直接让最快的人 ，来回跑送人过桥~可是后来实例一推就发现并不是总的最优的算法，
我们先将所有人按花费时间递增进行排序，假设前i个人过河花费的最少时间为opt[i]，那么考虑前i-1个人过河的情况，即河这边还有1个人，河那边有i-1个人，并且这时候手电筒肯定在对岸，所以
opt[i] = opt[i-1] + a[1] + a[i] (让花费时间最少的人把手电筒送过来，然后和第i个人一起过河)
如果河这边还有两个人，一个是第i号，另外一个无所谓，河那边有i-2个人，并且手电筒肯定在对岸，所以2、区间模型
opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2] (让花费时间最少的人把电筒送过来，然后第i个人和另外一个人一起过河，由于花费时间最少的人在这边，所以下一次送手电筒过来的一定是花费次少的，送过来后花费最少的和花费次少的一起过河，解决问题)
所以

opt[i] = min{opt[i-1] + a[1] + a[i] , opt[i-2] + a[1] + a[i] + 2*a[2] }

2.区间模型

区间模型的状态表示一般为d[i][j]，表示区间[i, j]上的最优解，然后通过状态转移计算出[i+1, j]或者[i, j+1]上的最优解，逐步扩大区间的范围，最终求得[1, len]的最优解。

  【例题7】给定一个长度为n（n <= 1000）的字符串A，求插入最少多少个字符使得它变成一个回文串。

典型的区间模型，回文串拥有很明显的子结构特征，即当字符串X是一个回文串时，在X两边各添加一个字符’a’后，aXa仍然是一个回文串，我们用d[i][j]来表示A[i…j]这个子串变成回文串所需要添加的最少的字符数，那么对于A[i] == A[j]的情况，很明显有 d[i][j] = d[i+1][j-1] （这里需要明确一点，当i+1 > j-1时也是有意义的，它代表的是空串，空串也是一个回文串，所以这种情况下d[i+1][j-1] = 0）；当A[i] != A[j]时，我们将它变成更小的子问题求解，我们有两种决策：
1、在A[j]后面添加一个字符A[i]；
2、在A[i]前面添加一个字符A[j]；
根据两种决策列出状态转移方程为：

 d[i][j] = min{ d[i+1][j], d[i][j-1] } + 1;

3.背包模型

摘选背包九讲各个类型

01背包
        有N种物品（每种物品1件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。
决策为第i个物品在前i-1个物品放置完毕后，是选择放还是不放，状态转移方程为：

f[i][v] = max{ f[i-1][v], f[i-1][v - Ci] +Wi }

（空间复杂度可利用滚动数组进行优化达到O(V)）。

f[[v] = max{ f[v], f[v - Ci] +Wi }

完全背包
           有N种物品（每种物品无限件）和一个容量为V的背包。放入第 i 种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。
           f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。

f[i][v] = max{ f[i-1][v - kCi] + kWi | 0 <= k <= v/Ci }

(当k的取值为0,1时，这就是01背包的状态转移方程）
时间复杂度O( VNsum{V/Ci} )，空间复杂度在用滚动数组优化后可以达到O( V )。
进行优化后（此处省略500字），状态转移方程变成：

f[i][v] = max{ f[i-1][v], f[i][v - Ci] +Wi }

时间复杂度降为O(VN)。

多重背包
           有N种物品（每种物品Mi件）和一个容量为V的背包。放入第i种物品耗费的空间是Ci，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。

f[i][v]表示前i种物品恰好放入一个容量为v的背包可以获得的最大价值。
f[i][v] = max{ f[i-1][v - kCi] + kWi | 0 <= k <= Mi }
时间复杂度O( Vsum(Mi) )，空间复杂度仍然可以用滚动数组优化后可以达到O( V )。
优化：采用二进制拆分物品，将Mi个物品拆分成容量为1、2、4、8、… 2^k、Mi-( 2^(k+1) - 1 ) 个对应价值为Wi、2Wi、4Wi、8Wi、…、2^kWi、（Mi-( 2^(k+1) - 1 )）Wi的物品，然后采用01背包求解。
这样做的时间复杂度降为O(Vsum(logMi) )。