• 算法认识
• 算法性质
• 步骤实战
  • 斐波那契式子
  • 硬币凑钱
• 例题实战
  • 爬楼梯
  • 最小路径和
  • 不同路径
• 适用场景
• 算法局限

算法认识

动态规划（Dynamic Programming）简称 DP，对于子问题重叠的情况特别有效，因为它将子问题的解保存在表格中，当需要某个子问题的解时，直接取值即可，从而避免重复计算。

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。

所以动态规划实际上是将问题分化成很多的子问题，然后将当前子问题计算过的最优结果存储起来，当另一个子问题也打算求该结果时，直接返回即可，因为已经是最优解。

动态规划的题目分为两大类，一种是求最优解类，典型问题是背包问题，另一种就是计数类，它们都存在一定的递推性质。前者的递推性质还有一个名字，叫做 「最优子结构」 ——即当前问题的最优解取决于子问题的最优解，后者类似，当前问题的方案数取决于子问题的方案数。所以在遇到求方案数的问题时，我们可以往动态规划的方向考虑。

算法性质

动态规划有很多的「高大上」的术语和性质，这些性质也是算法需要考虑的步骤。

子问题重叠

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

也就是在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解。

状态转移方程

动态规划最难的就是求解出状态转移方程，就类似于递推的公式，如：

f(n) = f(n - 1) + f(n - 2)  // n 是 1,2,...,n
dp[i] = dp[i - 1] + dp[i - 2]  // // i 是 1,2,...,i

其中 f(n) 由 f(n - 1) 和 f(n - 2) 不断转移，直至 n 才得到结果，这就是状态转移方程。

最优子结构

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。

原问题的解是由多个子问题的最优解构成，比如说，原问题是考出最高的总成绩，那么子问题就是要把语文考到最高，数学考到最高等，为了每门课考到最高，要把每门课相应的选择题分数拿到最高，填空题分数拿到最高等等，当然，最终就是每门课都是满分，这就是最高的总成绩。所以得到了最后正确的结果：最高的总成绩就是总分。

无后效性

即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

如 A -> B -> C，那么 B 和 C 的结果不会影响 A，同理 C 不会影响 B，但是 A 能影响 B 和 C，毕竟 B 和 C 是通过 A 的结果来算出。

自底向上

动态规划的特点就是从最底部（0 或者 1）蔓延到上面（n），假设存在长度 n，我们知道递归是从 n 到 n - 1 往下遍历，直至到 1，这叫 自顶向下。而动态规划是 自底向上，也就是从 1 到 2 往上遍历，直至到 n。

初始条件

因为动态规划是自底向上，所以我们在求解的时候需要由一些原始条件，如：

dp[0] = 0;
dp[1] = 1;

这样才有具体的值来自底向上：

dp[n] = dp[n - 1] + dp[n - 2];

步骤实战

动态规划遵循一套固定的流程：递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法。这个过程是层层递进的解决问题的过程，如果没有前面的铺垫，直接看最终的非递归的动态规划解法，会难理解。

斐波那契式子

斐波那契式子为：F(0) = 0，F(1) = 1, F(n) = F(n - 1) + F(n - 2)。

暴力的递归算法

public int fib(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fib(n - 1) + fib(n - 2); // 自顶向下
}

要想计算原问题 f(20)，就得先计算出子问题 f(19) 和 f(18)，然后要计算 f(19)，我就要先算出子问题 f(18) 和 f(17)，依次类推。最后遇到 f(1) 或者 f(2) 的时候，结果已知，就能直接返回结果。

子问题个数为 O(2^n)，所以这个算法的时间复杂度为 O(2^n)，效率很低。

这就是我们需要解决动态规划问题的第一个性质：重叠子问题

步骤二、带备忘录的递归解法

即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；后面每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

「备忘录」可以是数组，也可以是哈希表，key 为子问题的唯一标识，value 就是解决后的结果。

public int fib(int n) {
    if (n < 1) {
        return 0;
    }
    // 备忘录全初始化为 0
    int[] memo = new int[n + 1];
    memo[0] = 1;
    memo[1] = 1;
    // 初始化最简情况
    fibMemo(memo, n);
    return memo[n - 1];  // 1 1 2 3 5 8 13，因为 i 从 0 开始，所以 n - 1 就是结果
}

public int fibMemo(int[] memo, int n) {
    // 未被计算过
    if (n > 0 && memo[n] == 0) {
        memo[n] = fibMemo(memo, n - 1) + fibMemo(memo, n - 2);
    }
    return memo[n];
}

带「备忘录」的递归算法，把一棵存在巨量冗余的递归树通过「剪枝」，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

子问题个数为 O(n)。所以，本算法的时间复杂度是 O(n)。比起暴力算法，效率大幅度提升很多。

至此，带备忘录的递归解法的效率已经和动态规划一样了。实际上，这种解法和动态规划的思想已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」，这也是为什么动态规划一般都脱离了递归，而是由循环迭代完成计算。

动态规划

有「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，叫做 dp，在这张表上完成「自底向上」的推算。

public int fib(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
    }
    return dp[n - 1];  // 1 1 2 3 5 8 13，因为 i 从 0 开始，所以 n - 1 就是结果
}

dp[i] = dp[i - 1] + dp[i - 2]; 就是 状态转移方程，它是解决问题的核心。我们也很容易发现，其实状态转移方程直接代表着暴力解法。

动态规划问题最困难的就是写出状态转移方程。

动态规划优化

根据斐波那契数列的状态转移方程，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 dp 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

public int fib(int n) {
    if (n < 2) {
        return n;
    }
    int prev = 0, curr = 1;
    for (int i = 0; i < n - 1; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

硬币凑钱

给 k 种面值的硬币，面值分别为 c1，c2，...，ck，再给一个总金额 n，问最少需要几枚硬币凑出这个金额，如果不可能凑出，则回答 -1 。

比如说，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1。

暴力的递归算法

public int coinChange(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int ans = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 金额不可达
        if (amount - coin < 0) {
            continue;
        }
        int subProb = coinChange(coins, amount - coin);
        // 子问题无解时
        if (subProb == -1) {
            continue;
        }
        ans = Math.min(ans, subProb + 1);
    }
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

总时间复杂度为 O(k*n^k)。

带备忘录的递归算法

public int coinChange(int[] coins, int amount) {
    // 备忘录初始化为 -2
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, -2);
    
    return helper(coins, amount, memo);
}
public int helper(int[] coins, int amount, int[] memo) {
    if (amount == 0) {
        return 0;
    }
    // 备忘录不为 -2 代表已经存有最优解
    if (memo[amount] != -2) {
        return memo[amount];
    }
    int ans = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 金额不可达
        if (amount - coin < 0) {
            continue;
        }
        int subProb = helper(coins, amount - coin, memo);
        // 子问题无解时
        if (subProb == -1) {
            continue;
        }
        ans = Math.min(ans, subProb + 1);
    }
    // 记录本轮答案，下标就是凑够当前硬币的最少枚次数
    memo[amount] = (ans == Integer.MAX_VALUE) ? -1 : ans;
    return memo[amount];
}

动态规划

如果我们有面值为 1 元、3 元和 5 元的硬币若干枚，如何用最少的硬币凑够 11 元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如 1 元换成 2 元的时候)

如何用最少的硬币凑够i元（i < 11）？ 两个原因：

• 当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论
• 这个规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的， 本质上它还是同一个问题（规模变小后的问题其实是原问题的子问题）

当 i = 0，即需要多少个硬币来凑够 0 元。 由于 1，3，5 都大于 0，即没有比 0 小的币值，因此凑够 0 元最少需要 0 个硬币。这时候可以用一个 标记 来表示「凑够 0 元最少需要 0 个硬币」。

那么， 我们用 d(i) = j 来表示凑够 i 元最少需要 j 个硬币。于是我们已经得到了 d(0) = 0，表示凑够 0 元最小需要 0 个硬币。

当 i = 1 时，只有面值为 1 元的硬币可用，因此我们拿起一个面值为 1 的硬币，接下来只需要凑够 0 元即可，即 d(0) = 0。所以有：

d(1) = d(1 - 1) + 1 = d(0) + 1 = 0 + 1 = 1

当 i = 2 时，仍然只有面值为 1 的硬币可用，于是我拿起一个面值为 1 的硬币，接下来我只需要再凑够 2 - 1 = 1 元即可， 所以有：

d(2) = d(2 - 1) + 1 = d(1) + 1 = 1 + 1 = 2

当 i = 3 时，我们能用的硬币就有两种了：1 元和 3 元。既然能用的硬币有两种，于是就有两种方案。如果我拿了一个 1 元的硬币，我的目标就变为了： 凑够 3 - 1 = 2 元需要的最少硬币数量。即

d(3) = d(3 - 1) + 1 = d(2) + 1 = 2 + 1 = 3

这个方案说的是，我拿 3 个 1 元的硬币；第二种方案是我拿起一个 3 元的硬币，我的目标就变成：凑够 3 - 3 = 0元需要的最少硬币数量。即

d(3) = d(3 - 3) + 1 = d(0) + 1 = 0 + 1 = 1

这个方案说的是，我拿 1 个 3 元的硬币。

这两种方案哪种更优呢？题目要求使用用最少的硬币数量来凑够 3 元的。所以，选择 d(3) = 1，所以我们得到了 转移状态方程：

d(3) = Math.min(d(3 - 1) + 1, d(3 - 3) + 1);

从以上的文字中， 我们要得到动态规划里非常重要的两个概念：状态 和 状态转移方程。

上文中 d(i) 表示凑够 i 元需要的最少硬币数量，我们将它定义为该问题的 状态， 这个状态是怎么找出来的呢？要根据子问题定义状态，找到子问题，状态也就浮出水面了。最终我们要求解的问题，可以用这个状态来表示：d(11)，即凑够 11 元最少需要多少个硬币。

那状态转移方程是什么呢？既然我们用 d(i) 表示状态，那么状态转移方程应该包含了状态 d(i)，上文中包含状态 d(i) 的方程是：

d(3) = Math.min(d(3 - 1) + 1, d(3 - 3) + 1);

于是它就是状态转移方程，描述状态之间是如何转移的。当然，我们要对它抽象一下，

d(i) = Math.min(d(i), d(i - vj) + 1 ); // 其中 i-vj >= 0，vj 表示第 j 个硬币的面值

所以最终代码：

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 在求所有子问题 + 1 的最小值
        for (int coin : coins) {
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]); // 状态转移方程
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

例题实战

爬楼梯

下面介绍先通过典型的动态规划题目总结 计算步骤，然后利用计算步骤完成动态规划的题目。

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

如 n = 2 时，有两种方法，分别是：

• 1 阶 + 1 阶
• 直接 2 阶

如 n = 3，有三种方法，分别是：

• 1 阶 + 1 阶 + 1 阶
• 1 阶 + 2 阶
• 2 阶 + 1 阶

计算步骤

• 特例确定，也就是「剪枝」，判断满足某些条件，直接返回，不需要计算，一般针对起始位置或末尾位置
• 状态定义：定义状态的空间位置，确保动态规划有足够的空间存放子问题的解，如下题 f[i] 代表走过 i 阶需要的总方法
• 初始状态，动态规划自底向上，所以底部（0 或者 1）至少要有一个已知的值，然后慢慢推到后面的值
• 状态转移方程，动态规划最难的就是求解出状态转移方程，这是一种递推规律的公式
• 返回值：确定最终的返回值

简单动态规划

public int climbStairs(int n) {
    // 特例
    if(n <= 2) {
        return n;
    }
    // 确定空间
    int[] f = new int[n];
    // 初始条件
    f[0] = 1; // -1 才是没有楼梯
    f[1] = 2;
    // 转移方程
    for(int i = 2;i < f.length; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    return f[n - 1];
}

优化动态规划

因为我们只需要 3 中状态，也就是只需要 3 种子问题的解，即 n、n - 1、n - 2，其他的不需要，所以就利用变量来替换

public int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q; 
        q = r; 
        r = p + q;
    }
    return r;
}

最小路径和

题目来自 https://leetcode-cn.com/problems/minimum-path-sum/

解题思路参考：https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-dong-tai-gui-hua-gui-fan-liu-c/

题目

• 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小

• 说明：每次只能向下或者向右移动一步

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

此题是典型的动态规划题目。

下面按动态规划的步骤进行计算：

特例确定

如果 DP 长度为 0，返回 0。

状态定义

设 DP 为大小 m x n 矩阵，其中 dp[i][j] 的值代表直到走到 (i,j) 的最小路径和。

初始状态

DP 初始化即可，不需要赋初始值。

状态转移方程

题目要求，只能向右或向下走，换句话说，当前单元格 (i, j) 只能从左方单元格 (i−1, j) 或上方单元格 (i, j−1) 走到，因此只需要考虑矩阵左边界和上边界。

走到当前单元格 (i, j) 的最小路径和 =「从左方单元格 (i-1, j) 与从上方单元格 (i, j−1) 走来的两个最小路径和中较小的」 + 当前单元格值 dp[i][j] 。具体分为以下 3 种情况：

• 矩阵的第一列进行求和，然后覆盖原来的值。

  dp[i][0] += dp[i - 1][0];
  

• 矩阵的第一行进行求和，然后覆盖原来的值。

  dp[0][i] += dp[0][i - 1];
  

• 当左边和上边都不是矩阵边界时： 即当 i、j 不等于 0 时，有

  dp[i][j] += Math.min(dp[i - 1][j], dp[i][j - 1]);
  

返回值

返回 DP 矩阵右下角值，即走到终点的最小路径和。

复杂度分析

时间复杂度 O(M x N)：遍历整个 grid 矩阵元素。

空间复杂度 O(1)：直接修改原矩阵，不使用额外空间。

代码

grid 代表 DP

class Solution {
    public int minPathSum(int[][] grid) {
        int high = grid.length;
        int width = grid[0].length;
        if (width == 0) {
            return 0;
        }
        // 先将矩阵 [0] 的左右进行叠加
        for (int i = 1; i < high; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        for (int i = 1; i < width; i++) {
            grid[0][i] += grid[0][i - 1];
        }
        for (int i = 1; i < high; i++) {
            for (int j = 1; j < width; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        return grid[high - 1][width - 1];
    }
}

不同路径

题目来自：https://leetcode-cn.com/problems/unique-paths/

题目

• 一个机器人位于一个 m x n 网格的左上角

• 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，即 m x n 的终点（对角线的末尾）

• 问总共有多少条不同的路径？

下面按动态规划的步骤进行计算：

特例确定

无特例。

初始状态

DP 初始化即可，不需要赋初始值。

状态定义

设 m x n 矩阵有 dp[i][j]，其中 i 代表矩阵的第 i 行，j 代表第 j 列。

状态转移方程

规律：

• 如果位置处于第一行或者第一列，则总路径 = 1
• 不在第一行或者第一列，则某个位置的总路径 = 它上面位置的总路径 + 它左侧位置的总路径

状态转移方程为：

dp[m][n] = dp[m - 1][n] + dp[m][n - 1];

返回值

返回 DP 矩阵右下角值，即走到终点的总路径和。

复杂度分析

时间复杂度 O(m x n)：遍历整个 DP 矩阵元素。

空间复杂度 O(n)：直接修改原矩阵，不使用额外空间。

代码

public int uniquePaths(int m, int n) {
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 起始点为 0，如果在起始点的左侧或者右侧，那么就只有一条路径
            if (i == 0 || j == 0) {
                dp[i][j] = 1;
            }
            // 每条路径的次数都是从上方的路径和左侧的路径相加而得到，具体画图
            else {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }
    // 返回最后一个元素，数组从 0 开始
    return dp[m - 1][n - 1];
}

适用场景

适合用动态规划来解决的问题，都具有下面三个特点：最优化原理、最优化原理、有重叠子问题。

如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。某阶段状态（定义的新子问题）一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与其以前的状态有关。子问题之间是不独立的（分治法是独立的），一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）。

算法局限

动态规划对于解决多阶段决策问题的效果是明显的，但是动态规划也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。因而，受计算机的存贮量及计算速度的限制，当今的计算机仍不能用动态规划方法来解决较大规模的问题，这就是「维数障碍」。

动态规划大部分都是 空间换时间，因为动态规划需要一个 DP 来存已经计算的子问题的解，所以需要利用大量的空间来存解值，但是在时间上就很快找出该解值，不需要重新求解值。