动态规划（Dynamic Programming）

1 动态规划的基本思想

与分治法类似，动态规划的基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
与分治法不同之处在于：经分解得到的子问题往往不是相互独立，大量子问题会重复出现，不同子问题的数目常常只有多项式量级 。用分治法求解，将有许多子问题被重复计算。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

2 动态规划的性质

1. 最优子结构性质 。如果问题的最优解所包含的子问题的解也是最优的 ，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 重叠子问题 性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时 ，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）
3. 无后效性 ：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

3 动态规划算法求解步骤

动态规划算法求解的方式有两种：①自顶向下的备忘录法 ，②自底向上 ，可以在4.1节的内容中体会这两种方式的差别。
一般来说由于自顶向下备忘录方式的动态规划方法使用了递归，递归的时候会产生额外的开销，使用自底向上的动态规划方法要比备忘录方法好。下面给出了自底向上动态规划算法的设计步骤。

通常按照四步骤设计动态规划算法：

1. 找出最优解的性质，并刻画其结构特征
2. 递归定义求最优值的公式
3. 以自底向上计算最优值
4. 根据计算最优值时得到的信息，构造最优解

4 动态规划实例

这里给出了适合用动态规划解决的三个经典问题：斐波那契数列、最大子段和以及0-1背包问题。

4.1 斐波那契(Fibonacci)数列

斐波那契数列，又称黄金分割数列，其递推定义如下所示：

该问题用递归的方式实现非常简单：

    public int fib(int n)
    {
    if(n<=0)
        return 0;
    if(n==1)
        return 1;
    return fib( n-1)+fib(n-2);
    }
    // 输入：6
    // 输出：8

输入为6时，算法执行的递归树如下图所示。

上图所示的递归树中，有很多节点被重复执行，如fib(2)被重复执行了5次。由于调用每一个函数的时候都要保留上下文，所以空间上开销也不小。这么多的子节点被重复执行，如果在执行的时候把执行过的子节点保存起来，后面要用到的时候直接查表调用的话可以节约大量的时间。
①自顶向下的备忘录法求解斐波那契数列
创建一个n+1大小的数组来保存求出的斐波拉契数列中的每一个值，在递归的时候如果发现前面fib(n)的值计算出来了就不再计算，否则计算出来后保存在Memo数组中，下次再调用fib(n)的时候就不需要重新递归了。

    int Fibonacci(int n)
    {
    if(n <= 0) {
    		return n;
    	}
    	vector<int> Memo(n + 1, 0);
    for(int i = 0; i <= n; ++i)
        Memo[i] = -1;
    return fib(n, Memo);
    }
    int fib(int n, vector<int> Memo)
    {
    if(Memo[n] != 0)
        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];
    }
    }

②自底向上的方法求解斐波那契数列
先计算子问题，再由子问题计算父问题。

    int fib(int n)
    {
    if(n <= 1) {
    	return n;
    }
    int Memo_i_2 = 0;
    int Memo_i_1 = 1;
    int Memo_i = 1;
    for(int i = 2; i <= n; ++i)
    {
        Memo_i = Memo_i_2 + Memo_i_1;
        Memo_i_2 = Memo_i_1;
        Memo_i_1 = Memo_i;
    }       
    return Memo_i;
    }

从子问题开始自底向上计算，直到得到结果，过程中不需要递归，也不需要额外创建长度为 n+1 的数组用于存放子问题的结果。

4.2 最大子段和问题

问题描述：

1. 给定由N个整数（可能有负整数）组成的序列 a1，a2，…，an，求该序列形如 ai + ai+1 +…+ aj 的子段和的最大值。
2. 当所有整数均为负整数时，定义其最大子段和为0。
3. 例如：当{ a1, a2, …, a6 }={-1，11，-4，13，-5，-2}时，其最大子段和为20。

其最优子结构的定义如下所示：

最大子段和的结果为：

    int MaxSum(int a[], int n)
    { //时间复杂度O(n)
    int sum = 0,b = 0;
    for(j = 1; j <= n; ++j)
    {
        if (b > 0)  b += a[j]; 
        else b = a[j];
        if(b > sum) { sum = b; }
        return sum;
    }
    }

4.3 0-1背包问题

问题描述：

1. 给定 n 种物品和一背包。物品 i 的重量是 wi，其价值为vi，背包的容量为 C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
2. 选择装入背包的物品时，对每种物品i只有2种选择，即装入或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

问题的形式化描述如下：

m(i, j) 表示背包容量为 j ，可选择物品为 i, i+1, …, n 时0-1背包问题的最优值。由最优子结构，m(i, j) 的定义式为：

    int PackageHelper(int n, vector<int> w, vector<int> p, int v) {
    	//设置一个二维数组，横坐标代表从第一个物品开始放到第几个物品，纵坐标代表背包还有多少容量，dp代表最大价值
    	vector<vector<int>> dp(n+1, vector<int>(v+1, 0));
    	for(int i = 1; i < n+1; ++i){
    		for(int j = 1; j <= v; ++j){
    			if(j >= w[i]){
    				/* * 当能放得下这个物品时，放下这个物品，价值增加，但是空间减小，最大价值是dp[i-1][j-w[i]]+p[i]
    				* 当不放这个物品时，空间大，物品还是到i-1，最大价值是dp[i-1][j]
    				* 比较这两个大小，取最大的，就是dp[i][j]
    				*/
    				dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
    			}else{
    				//如果放不下，就是放上一个物品时的dp
    				dp[i][j] = dp[i-1][j];
    			}
    		}
    	}
    	return dp[n][v];
    }