vlambda博客
学习文章列表

动态规则是算法中非常重要的一类方法，书本上很多都是列出一堆公式，如果是初学者需要花费很多心血练习之后，才会有那么一刻有顿悟的感觉！本文希望通过使用王者峡谷二位脆皮英雄对话的方式讲解动态规划，让大家在轻松愉快的氛围中搞懂动态规划。

后续会持续更新算法：重点讲 排序、递归、回溯、贪心、深度/广度优先搜索等，顺序不定，希望尽早了解的可以给我留言。

鲁班：安琪拉，你听过动态规划吗？

安琪拉：当然听说过，王者峡谷有个传闻，谁掌握了动态规划，就相当于拿到了屠龙刀，可以biubiubiu 三下砍死大龙。

鲁班：安琪拉妹妹，你能给我讲讲什么是动态规划吗？

安琪拉：鲁班哥哥，看你求知欲这么强，咱俩又都是脆皮的份上，我给你讲讲动态规划。

鲁班：已经搬好小板凳。

安琪拉：动态规划是一种求问题最优解的方法。通用的思路：将问题的解转化成==> 求解子问题，==> 递推，==>最小子问题为可直接获得的初始状态。

鲁班：你这么说完我还是很蒙啊！能不能不打嘴炮，给我演示一下这个技能呗！

安琪拉：可以啊！我们找个小怪演示一下，请看第一题（斐波拉契数列）：

这个数列特点是从第三项开始，每一项都是前二项的和：2 = 1 + 1，3 = 1 + 2；

鲁班：这个我知道怎么做，你看我的，手写代码在此：

public class FibonacciSequence {
  //求斐波拉契第n项
    public int fibonacci(int n){
        if(n == 1 || n == 2){
            return 1;
        }else{
            return fibonacci(n-1) + fibonacci(n-2);
        }
    }
}

安琪拉：你这个解法其实就有动态规划的思想，但是还可以做些优化！因为中间有大量的重复计算。

比如，我们求数列中第100个数是多少？递归会如下所示：

安琪拉：如👆图所示，当求第100个斐波拉契数时，需要求第99 个和第 98个，在计算第99 个时获得98之后，因为没有把第98项的结果保存下来，求第98 项时需要重新计算一次。同理，第97 项的计算也需要计算二次，依次类推，这其中存在大量重复计算。

鲁班：我发现了，求第n 个数，前n - 2 个数都会重复计算，时间复杂度为O( )，那这个问题怎么解决呢？

安琪拉：使用动态规划，非常适合解决这类问题，动态规划也有区分，一种是通过Map将中间结果保存起来，等到第二次求的时候直接从Map中获取，还有一种只保留用于推导下一个值的最小数据，如下：

public int fibonacciDP(int n){
  if( n <= 2) {
    return 1;
  }
  //保存前一项 以及 前前一项
  int pre = 1, prepre = 1;
  int index = 3;
  int cur = pre + prepre;
  while (index <= n){
    //通过前一项和前前一项 得到当前值
    cur = pre + prepre;
    prepre = pre;
    pre = cur;
    index++;
  }
  return cur;
}

鲁班：原来是这样，把已经求过的值保存起来，后面的值根据前面的值推导出来，这样不需要重复计算子问题，时间复杂度降低为 O (n) 了，妙啊！

安琪拉：这个就是典型的使用动态规划求解，鲁班哥哥，我们先总结可以动态规划求解问题的特点，待会再多看一些典型的问题。可以动态规划求解问题的特点有二：

1. 需要求解的问题具有 相似子问题，重点在相似二个字，例如上面的求第100个数需要第99 和 第 98 个数，求第 99 个数需要求第 98 和第 97个数，求解子问题具有相似性；
2. 需要求解的结果或最优结果由子问题的结果或最优结果推导而来，例如： F（n）= F（n-1）+ F（n-2）

鲁班：哦哦，那我以后可以通过这二个特点判断问题是否可以通过动态规划求得。

安琪拉：是的，另外求动态规划问题，也是有固定套路的，一般步骤如下：

1. 定义 数组或 变量保存历史记录，避免重复计算，一般程序中都用 dp[]定义，定义数组元素或变量的含义；
2. 找到 数组元素之前的关系，这一步是最关键的，例如我们上面计算dp[n] 时，可通过dp[n-1] 和 dp[n-2] 获得；
3. 找到计算的起点以及值，例如上面斐波拉契数列的起点为 第一项 ：1，第二项：1，因为起点决定终点 😆。

鲁班：安琪拉妹妹，我好像已经学到精髓了，我五脏六腑的真气快憋不住了，快出几道题让我去去火。

安琪拉：那我讲几道典型的动态规划题目出给你，请👂题。

题目一：爬楼梯

假设你正在爬楼梯。从楼底到楼顶总共100 级台阶。

每次你可以选择跨1 个或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

鲁班：那我按照上面你教我的，判断一下这个问题是否适合通过动态规划求解：

1. 需要求解的问题具有 相似子问题：爬100 级台阶的走法和爬99 级台阶走法都是跨1 、2 步求得，满足这个需求；
2. 需要求解的结果或最优结果由子问题的结果或最优结果推导而来，爬100 级台阶可以通过 爬完99 级台阶 + 跨1 步 这种走法 加 爬完98 级台阶 + 跨2步来完成，可以以此类推，满足特点；

安琪拉：通过二个特点验证了这个问题可通过动态规划求解，再试试通过三步骤把这个问题解出来吧。

鲁班：好的, 三步骤如下：

• 第一步：定义数组或变量，我定义一个dp[100] 分别保存 爬1级台阶走法，爬2级台阶走法 … 爬100级台阶的走法；

• 第二步：找元素的关系，爬到第n 级台阶的走法有二种：

  因此总的走法为 dp[n] = dp[n-1] + dp[n-2]

1. 从第 n -1 级台阶 走 1 级上来
2. 从第 n -2 级台阶 走 2 级上来

• 第三步：找到计算的起点，

1. 当n = 1时，只有1 级台阶，只能1步跨上来，因此dp[1] = 1；
2. 当n = 2时，有2级台阶，可以直接1步跨2级 或 一次跨1级走2步，以此dp[2] = 2;

实现代码：

public void climbStairs() {
  //1. 定义数组或变量
  long[] dp = new long[101];
  //3. 找到计算的起点
  dp[1] = 1;
  dp[2] = 2;

  int index = 3;
  while (index <= 100){
    //2. 找元素的关系 
    dp[index] = dp[index-1] + dp[index-2];
    index++;
  }

  System.out.println(dp[100]);
}

安琪拉：你看下，如果台阶数从100 变成 n，你的空间复杂度是 O（n），这个你觉得还有可优化的空间吗？

鲁班：我想想，好像数组不需要这么大，求 dp[n] 只需要用到前二个数 dp[n-1] 和 dp[n-2], 我只需要定义二个变量就好了，这就改代码，如下：

/**
  * 爬楼梯
  * @param n 台阶数
  * @return
*/
public long climbStairs(int n) {
  if(n == 1 || n == 2){
    return n;
  }
  //1. 定义数组或变量  3. 找到计算的起点
  // dp_n_2 代表 dp[n-2]; dp_n_1代表 dp[n-1];
  long dp_n_2 = 1; 
  long dp_n_1 = 2;

  int index = 3;
  long cur = dp_n_1 + dp_n_2;
  while (index <= n){
    //2. 找元素的关系
    cur = dp_n_1 + dp_n_2;
    dp_n_2 = dp_n_1;
    dp_n_1 = cur;
    index++;
  }

  return cur;
}

安琪拉：不错不错，空间复杂度从 O (n) 降到只有 O (1), 我们再来看个稍微复杂一点的动态规划问题。

题目二：最小路径和

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

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

输入: 
[
 [1,3,1],
 [1,5,1],
 [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
**备注**：输入定义为 value[m][n] 二维数组 m 行 n 列，这里 m，n都为3

鲁班：你都说了是动态规划问题，我就不用二特性验证是否可以用动态规划求解，直接通过三步骤解决问题了：

• 第一步：定义数组或变量，我定义一个dp[m][n]  的二维数组保存数组中任一位置到左上角起点的最小路径和；

• 第二步：找元素的关系，任意选取一个元素，看一下这个元素的值怎么求得，以选取终点为例，看下图：

  除终点元素，其他元素也符合这个规则，但是需要考虑边界问题，如果元素没有左元素或者上元素，只需要简单直接以左元素或者上元素中有的元素最小路径和 + 当前元素值。

1. 因为条件限定了只能往右和往下走，如果要到终点，只能从UP元素或者Left元素过来，UP元素代表上方的元素，Left元素代表左侧元素，元素名是我自己给起的，为了方便说明；

2. 那终点元素的值 =  Math.min( UP元素的最小路径和 , Left元素最小路径和 ) + 终点元素的值（这里是1）；

   泛化成公式：dp[m] [n] =  Math.min( dp[m-1] [n] ,dp[m] [n-1]) +  value[m] [n];

   所有动态规划的描述元素之间关系的公式都有个名字：状态转移方程

• 第三步：找到计算的起点，

1. dp[0] [0] 是左上角第一个元素，作为起点，因为不能别的元素过来，因此 dp[0] [0] = value[0] [0]；

实现代码如下：

public int minPathSum(int[][] grid) {
  //边界检查
  if(grid == null || grid.length < 1 || grid[0].length < 1){
    return 0;
  }
  //获取行数 和 列数
  int m = grid.length;
  int n = grid[0].length;
  // 1. 定义二维数组 保存数组每个元素到起点的最小路径和
  int[][] dp = new int[m][n];
  for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
      //2. 找元素的关系 & 考虑边界条件
      if(i == 0 && j == 0){
        //第一个元素，没有上元素，也没有左元素
        dp[0][0] = grid[0][0];
      }else if(i == 0){
        //没有上元素，只能从左元素走过来
        dp[i][j] = dp[i][j-1] + grid[i][j];
      }else if(j == 0){
        //没有左元素，只能从上元素走过来
        dp[i][j] = dp[i-1][j] + grid[i][j];
      }else{
        //既有上元素，也有左元素
        dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
      }
    }
  }
  //终点最小路径和
  return dp[m-1][n-1];
}

安琪拉：嗯嗯，不错，但是你看一下，时间复杂度是O(m * n), 空间复杂度是 O(m * n)，你觉得空间复杂度能否再优化，另外边界条件的判断那里我觉得也可以再优化。

鲁班：我明白了，跟之前的问题一样：

1. 当前元素的dp 值只跟前二个元素dp 值有关，我只需要保存推导当前元素所需要的dp值就可以了，不需要申请完整的m * n 的额外空间；
2. 我还可以把边界检查的顺序优化一下，因为 i = 0 或 j = 0 属于特殊情况，检查的判断条件后置，从编译的角度优先对最有可能进入的条件分支进行判断。

优化后程序如下：

public int minPathSum(int[][] grid) {
  //省下 m * n 的额外空间，前提：grid 二维数组允许值被覆盖
  for(int i = 0; i < grid.length; i++) {
    for(int j = 0; j < grid[0].length; j++) {
      //1. 最有可能的分支前置
      if(i != 0 && j != 0){
        grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
      }
      else if(i == 0)  grid[i][j] = grid[i][j - 1] + grid[i][j];
      else if(j == 0)  grid[i][j] = grid[i - 1][j] + grid[i][j];
      else continue;
    }
  }
  return grid[grid.length - 1][grid[0].length - 1];
}

安琪拉：不错不错，看来你掌握了动态规划的精髓，我们来看更加复杂一点的动态规划问题：

题目三：零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2:

输入: coins = [2], amount = 3 输出: -1说明: 你可以认为每种硬币的数量是无限的。

鲁班：【抓耳挠腮思考】这个好像问题有点复杂，不像前二题，我都找不出元素之前的关系，元素怎么定义也不清楚。😭

安琪拉：这种问题在动态规划中叫做求最优解空间，既要筹钱，又要使用的硬币数量最少，最关键的还是找到动态规划dp 怎么定义，以及dp 元素之前的关系。我们还是按照三步骤来：

• 第一步：定义dp数组或变量，首先明确题目说每种硬币的数量是无限的，但是会给定一个固定的 amount 金额，我们需要用最少的硬币数凑出这个金额，因此可以定义dp[n] 为需要凑出金额n 所需要的最小硬币数；

• 第二步：找元素的关系，假设现在需要求dp[11]（凑11块钱），现在手里有1，2，5块三种硬币，是不是10，9，6块钱都+ 1个硬币就可以凑齐11 块了（10块加1块，9块加2块，6块加5块）。那我们应该选10，9，6块中的哪一种呢？

  就看凑齐10，9，6三种金额哪种方式用到的硬币数量最少，dp(11) = Math.min( dp(10),  dp(9),  dp(6) ) + 1;

  我们试着开始推导一下状态转化方程：

1. dp[n] 为凑齐金额为n 所需要的最少硬币数量；
2. coins[] 为硬币种类数组，例如coins[3] = [1, 2, 5] 代表硬币种类为 1块，2块，5块；
3. 假设现在dp[0] ~ dp[n-1] 我们都求出来了，也就是凑齐0 ~ n-1元所需要的最少硬币数都知道了，现在dp[n] 怎么求？因为我们有1块，2块，5块钱，是不是很自然的想到凑齐n 元只需要从 dp[n-1] , dp[n-2], dp[n-5] 中选一个最小的 + 1。泛化状态转移方程：

• 第三步：找到计算的起点，dp[0] = 0 (凑齐0元不需要硬币)

实现代码如下：

public int coinChange(int[] coins, int amount) {
  //边界条件检查
  if(amount < 0){
    return -1;
  }
  if(amount == 0){
    return 0;
  }

  //1. 定义dp数组，dp[n]代表凑齐n元所属最小硬币数
  int[] dp = new int[amount+1];
  Arrays.fill(dp, amount+1);
  //3. 设置计算的起点
  dp[0] = 0;
  for(int i = 0; i <= amount; i++){
    //遍历所有硬币，试图找到最小硬币数的组合
    for(int coin : coins){
      if(i - coin >= 0){
        dp[i] = Math.min(dp[i], dp[i-coin]+1);
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount];
}

鲁班：原来dp[n] 还能这样定义，n直接当做金额下标，确实没有想到，通过n - coin(硬币面值) 确定作为状态转移。

安琪拉：我们多看几题巩固一下动态规划吧。

题目四：按摩师

一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

示例 1：

输入：[1,2,3,1] 输出：4 解释：选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例 2：

输入：[2,7,9,3,1] 输出：12 解释：选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。示例 3：

输入：[2,1,4,5,3,1,1,3] 输出：12 解释：选择 1 号预约、 3 号预约、 5 号预约和 8 号预约，总时长 = 2 + 4 + 3 + 3 = 12。

鲁班：这题看着不太像是满足动态规划的二个特点的。按摩师不能连续二天按摩跟动态规划有关系吗？

安琪拉：那我们来回顾一下动态规划的二个特点：

1. 需要求解的问题具有 相似子问题，例如：按摩师前天约了，今天才能约，如果昨天约过了，今天不能约，因此第n天接受预约能达到的最长预约时长为 Math.max( 第n-2天最长预约时间 +今天的时间，第n-1天最长预约时间)，子问题同样依赖此公式;
2. 需要求解的结果或最优结果由子问题的结果或最优结果推导而来，这里是： dp（n）= Math.max(dp（n-1), dp（n-2）+value(今天))，预约不连续。

鲁班：我似乎有点理解了，话不多说，直接撸代码吧！

public int massage(int[] nums) {
  if(nums == null || nums.length ==0){
    return 0;
  }
  if(nums.length < 2){
    return nums[0];
  }
  // 第一步：定义dp数组
  int[] dp = new int[nums.length];
  // 第三步：初始化起点
  dp[0] = nums[0];
  dp[1] = Math.max(dp[0], nums[1]);
  int i = 2;
  while( i < nums.length){
    // 第二步：状态转移方程
    dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
    i++;
  }
  return dp[nums.length-1];
}

安琪拉：写的不错，看来渐入佳境了，最后二题将今天的动态规划收尾吧！

题目五：打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1] 输出: 4 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1] 输出: 12 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

鲁班：啥话不说，写就完了。安琪拉妹妹请过目：

public int rob(int[] nums) {
  int len;
  //边界检查
  if(nums == null || (len = nums.length) == 0){
    return 0;
  }
  if(len == 1){
    return nums[0];
  }
  //第一步：定义dp变量
  int dp_pre = nums[0];
  int dp_cur = Math.max(dp_pre, nums[1]);
  int i = 2;
  int tmp;
  while(i < len){
    tmp = dp_cur;
    //状态转移方程
    dp_cur = Math.max(dp_pre +nums[i] , dp_cur);
    dp_pre = tmp;
    i++;
  }
  return dp_cur;
}

安琪拉：小偷这题有个变种，你可以思考一下，留作家庭作业，你看如何？

鲁班：放马过来

安琪拉：

题目六：打家劫舍2

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:

输入: [2,3,2] 输出: 3 解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例 2:

输入: [1,2,3,1] 输出: 4 解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

鲁班：soga，这个其实就是二选一，只能从第一家和最后一家选一个行窃，代码如下：

class Solution {
    public int rob(int[] nums) {
        int len;
        if(nums == null || (len=nums.length) == 0){
            return 0;
        }
        if(len == 1){
            return nums[0];
        }
        //不偷第一个 或  不偷最后一个
        return Math.max(
            myRob(Arrays.copyOfRange(nums, 0, nums.length-1)), 
            myRob(Arrays.copyOfRange(nums, 1, nums.length))
            );
    }

    private int myRob(int[] nums){
        int pre = 0;
        int cur = 0;
        int tmp;

        for(int item : nums){
            tmp = cur;
            cur = Math.max(pre + item, cur);
            pre = tmp;
        }
        return cur;
    }
}

安琪拉：看来你已经能熟练运用 二特性 三步骤 了，希望你以后能横行峡谷，所向披靡，别轻易被秒了！

鲁班：只要安琪拉妹妹不要草丛阴人，我还是很稳的！再见，下次你再教我别的算法技能吧！

安琪拉：关注【安琪拉的博客】，一切好说！

《安琪拉与面试官二三事》系列文章

《安琪拉教鲁班学算法》系列文章