动态规划（Dynamic programming）详解

动态规划（Dynamic programming，简称DP）是一种将复杂问题分解成很多子问题，并将子问题的求解结果存储起来避免重复求解的一种算法。动态规划一般用来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。最后通过一组决策序列（动态转移方程），产生最终期望的最优解。

能用动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

一、基本概念（动态规划的三个特征）

1. 最优化原理（最优子结构性质）：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2. 无后效性：将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3. 子问题的重叠性：如果有大量的重叠子问题，我们可以用空间将这些子问题的解存储下来，避免重复求解相同的子问题，从而提升效率。本质上，动态规划是一种以空间换时间的技术。

上面是摘自百度百科的解释，比较拗口。下面看看网上摘的另一个回答。

一个模型指的是动态规划适合解决的问题模型。我把这个模型定义为“多阶段决策最优解模型”。

1. 最优子结构：指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面状态推导出来。
2. 无后效性：无后效性，有两层含义，第一层含义是，在推导后面阶段状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。即已经求解的子问题，不会再受到后续决策的影响。
3. 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。即存在子问题进行了重复计算。

举例：比如要求年级考试最高分时，我们可以把这个问题拆分成求每个班级的最高分，最后再通过每个班级的最高分去求年级的最高分。这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。计算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。

再举个例子：假设学校有 10 个班，你已知每个班的最大分数差（最高分和最低分的差值），那么现在要计算全校学生中的最大分数差。此问题就不符合最优子结构，因为年级的最大分数差不能通过每个班级的最大分数差去计算出来（比如全校的最大分数差可能是 3 班的最高分和 6 班的最低分之差）。

对于这种最优子结构失效的情况，我们有时可以通过改造问题来使问题符合最优子结构。

最大分数差，等价于什么？不就是等价于最高分数和最低分数的差么？不就是第一个例子中的求最值问题么？那么不就是具有最优子结构了么？此时就可以改变思路，借助最优子结构解决最值问题，再回过头解决最大分数差问题。

参考：什么是最优子结构、如何判定 DP 数组的遍历方向 - 知乎

同分治法（Divide and Conquer）一样，动态规划也是将子问题的求解结果进行合并，其主要用在当子问题需要一次又一次地重复求解时，将子问题的求解结果存储到一张表中（称为动态规划表）以免重复计算。因此当没有公共的（交叠的、重叠的）子问题时，动态规划算法并不适用，因为没有必要将一个不再需要的结果存储起来。例如，二分搜索（折半查找）就不具有重叠的子问题性质。

二、从斐波那契数列求解分析动态规划

斐波那契数列（Fibonacci sequence）指的是这样的一组数列：0、1、1、2、3、5、8、13……，即当前数为前两个数值相加，用数学公式表达为：F(0)=0，F(1)=1，F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）。

使用递归算法求解斐波那契数列：

    public static int fib(int n) {
        if(n<=0) {
            return 0;
        } else if(n==1) {
            return 1;
        } else {
            return fib(n-1) + fib(n-2);
        }
    }

如下图（n = 6 时的斐波那契数列计算过程的递归树形结构），我们为了计算F(6)的值，重复计算了许多遍的F(4)、F(3)……，（这就是重复子问题）这也导致递归算法的效率是十分低下的。

那么，我们是否能采用动态归纳来优化呢？

首先，需要分析“斐波那契数列”问题能否满足动态规划的使用条件。

1. 最优子结构：F(n)的状态可以通过前面的状态推导出来。
2. 无后效性：已经求解的子问题，不会再受到后续决策的影响。
3. 重叠子问题：比如F(6)的求解，对于子问题F(4)进行了重复计算。

因此“斐波那契数列”问题可以使用动态规划去解决。那么具体应该怎么做呢？

基本思路

动态规划本质上是利用历史记录，来避免我们的重复计算。 而这些历史记录（动态规划表），我们需要一些变量来保存，一般是用一维数组或者二维数组来保存。下面我们来看看动态规划的基本思路。

1. 确定状态：将原问题划分为若干阶段，每个阶段对应若干个子问题，提取这些子问题的特征（称之为状态）；并且一般是从最后一步从底层一步一步往上逆推的。
2. 确定状态转移方程：寻找每一个状态的可能决策，或者说是各状态间的相互转移方式（用数学的语言描述就是 状态转移方程）。
3. 确定开始以及边界条件。
4. 按顺序求解每一个阶段的问题。

以“斐波那契数列”问题为例：

1. 确定状态：所谓的状态其实就是问题的数学描述。比如定义F(n)表示第n个斐波那契数列的值。

2. 确定状态转移方程式：假如我们不知道斐波那契数列的定义，就只有给定的一组数列（0、1、1、2、3、5、8、13……），我们一般通过观察归纳去总结每个状态之间的关系式。此时，F(n)=F(n-1)+F(n-2) 就是我们归纳出来的状态转移方程，F(n-1)和F(n-2) 就称为F(n)的最优子结构。

3. 确定开始以及边界条件：当有了状态转移方程式后，我们还需要明确初始值。此时，F(0)=0，F(1)=1就是边界条件。

更多可以参考：30分钟弄懂动态规划算法详细讲解(超详细) - it610.com

当以上思路理清后，我们就可以写代码了。

    public static int fib2(int n) {
        if(n <= 1)
            return n;
        // 先创建一个数组来保存历史数据
        int[] dp = new int[n+1];
        // 给出初始值
        dp[0] = 0;
        dp[1] = 1;
        // 通过关系式来计算出 dp[n]
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        // 把最终结果返回
        return dp[n];
    }

递归的时间复杂度是O(2^n)，而动态规划由于将重复子问题的结果存起来了，因此时间复杂度仅为O(n)。

三、另一个例子

一个机器人位于一个m × n的网格中，机器人每次只能向右或者向下走一步，求机器人达到右下角总共有多少种方式？

1. 确定状态：由于题目要求机器人从左上角到右下角有多少种方式，那么我们就定义dp[i][j]为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i] [j] 种路径。那么，dp[m-1][n-1]就是机器人走到右下角的所有方式（注意：数组下标从0开始）

2. 确定状态转移方程：想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人只能向下走或者向右走，所以有两种方式到达：一种是从 (i-1, j) 这个位置向下走一步到达；另一种是从(i, j - 1) 这个位置向右走一步到达。因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

3. 确定开始以及边界条件：当机器人处在[0][0]这个位置时，dp[0][0]为0，因为不需要走。当机器人处在边界处，即i=0或者j=0时，此时机器人只可能有一种方式，即一直向下走（j=0）或者一直向右走（i=0）

因此，动态规划代码如下：

    public static int uniquePaths(int m, int n) {
        if(m<=0 || n<=0)
            return 0;
        // 先创建一个数组来保存历史数据
        int[][] dp = new int[m][n];
        // 给出初始值
        dp[0][0] = 0;
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++){
            dp[0][i] = 1;
        }
        // 通过关系式来计算出 dp[m][n]
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }

四、参考文档

大厂面试常被问到的动态规划-技术圈

 动态规划基础 - OI Wiki

什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 知乎