Abo

动态规划集锦（Dynamic programming，简称DP）

发表于 | 分类于 | 热度 ℃
字数统计 3.9k | 阅读时长 15

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。


cover

动态规划问题一直是算法面试当中的重点和难点，并且动态规划这种通过空间换取时间的算法思想在实际的工作中也会被频繁用到


        

        


四个步骤
一般解决动态规划问题，分为四个步骤，分别是


    

  • 问题拆解，找到问题之间的具体联系
    • 

  • 状态定义
    • 

  • 递推方程推导
    • 

  • 实现
    • 



这里面的重点其实是前两个，如果前两个步骤顺利完成，后面的递推方程推导和代码实现会变得非常简单。


题目实战
爬楼梯
问题描述
但凡涉及到动态规划的题目都离不开一道例题：爬楼梯（LeetCode 第 70 号问题）


假设你正在爬楼梯。需要 n 阶你才能到达楼顶。


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


注意：给定 n 是一个正整数。


示例 1：


1
2
3
4
5
6
输入：2
输出：2
解释： 
有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶


示例 2：


1
2
3
4
5
6
7
输入：3
输出：3
解释： 
有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶


思考
爬楼梯，可以爬一步也可以爬两步，问有多少种不同的方式到达终点，我们按照上面提到的四个步骤进行分析：


    

  • 问题拆解：
    

    我们到达第 n 个楼梯可以从第 n - 1 个楼梯和第 n - 2 个楼梯到达，因此第 n 个问题可以拆解成第 n - 1 个问题和第 n - 2 个问题，第 n - 1 个问题和第 n - 2 个问题又可以继续往下拆，直到第 0 个问题，也就是第 0 个楼梯 (起点)
    

    • 

  • 状态定义
    

    “问题拆解” 中已经提到了，第 n 个楼梯会和第 n - 1 和第 n - 2 个楼梯有关联，那么具体的联系是什么呢？你可以这样思考，第 n - 1 个问题里面的答案其实是从起点到达第 n - 1 个楼梯的路径总数，n - 2 同理，从第 n - 1 个楼梯可以到达第 n 个楼梯，从第 n - 2 也可以，并且路径没有重复，因此我们可以把第 i 个状态定义为 “从起点到达第 i 个楼梯的路径总数”，状态之间的联系其实是相加的关系。
    

    • 

  • 递推方程
    

    “状态定义” 中我们已经定义好了状态，也知道第 i 个状态可以由第 i - 1 个状态和第 i - 2 个状态通过相加得到，因此递推方程就出来了 dp[i] = dp[i - 1] + dp[i - 2]
    

    • 

  • 实现
    

    你其实可以从递推方程看到，我们需要有一个初始值来方便我们计算，起始位置不需要移动 dp[0] = 0，第 1 层楼梯只能从起始位置到达，因此 dp[1] = 1，第 2 层楼梯可以从起始位置和第 1 层楼梯到达，因此 dp[2] = 2，有了这些初始值，后面就可以通过这几个初始值进行递推得到。
    

    • 



代码实现
1
2
3
4
5
6
7
8
9
10
11
public int climbStairs(int n) {
    if (n == 1) {
        return 1;
    }
    int[] dp = new int[n + 1];  // 多开一位，考虑起始位置
    dp[0] = 0; dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}


不同路径
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。


机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。


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


1


代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int uniquePaths(int m, int n) {
    if (m <= 0 || n <= 0) {
        return 0;
    }
    int[] dp = new int[n]; // 
      // 初始化
      for(int i = 0; i < n; i++){
      dp[i] = 1;
    }
        // 公式：dp[i] = dp[i-1] + dp[i]
    for (int i = 1; i < m; i++) {
        // 第 i 行第 0 列的初始值
        dp[0] = 1;
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j-1] + dp[j];
        }
    }
    return dp[n-1];
}


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


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


1
2
3
4
5
6
7
8
9
举例：
输入:
arr = [
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。


代码实现
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
public static int uniquePaths(int[][] arr) {
      int m = arr.length;
      int n = arr[0].length;
    if (m <= 0 || n <= 0) {
        return 0;
    }
    int[][] dp = new int[m][n]; // 
      // 初始化
      dp[0][0] = arr[0][0];
      // 初始化最左边的列
      for(int i = 1; i < m; i++){
      dp[i][0] = dp[i-1][0] + arr[i][0];
    }
      // 初始化最上边的行
      for(int i = 1; i < n; i++){
      dp[0][i] = dp[0][i-1] + arr[0][i];
    }
        // 推导出 dp[m-1][n-1]
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
        }
    }
    return dp[m-1][n-1];
}


最大正方形
问题描述
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。


示例:


1
2
3
4
5
6
输入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出: 4


思考
题目给定一个字符矩阵，字符矩阵中只有两种字符，分别是 ‘0’ 和 ‘1’，题目要在矩阵中找全为 ‘1’ 的，面积最大的正方形。


刚拿道这道题，如果不说任何解法的话，其实并不是特别好想，我们先来看看切题的思路是怎么样的。


首先一个正方形是由四个顶点构成的，如果说我们在矩阵中随机找四个点，然后判断该四个点组成的是不是正方形，如果是正方形，然后看组成正方形的每个位置的元素是不是都是 ‘1’，这种方式也是可行的，但是比较暴力，这么弄下来，时间复杂度是O((m*n)^4)。


那我们就会思考，组成一个正方形是不是必须要四个点都找到？如果我们找出其中的三个点，甚至说两个点，能不能确定这个正方形呢？


你会发现，这里我们只需要考虑 正方形对角线的两个点 即可，这两个点确定了，另外的两个点也就确定了，因此我们可以把时间复杂度降为 O((m*n)^2)。


但是这里还是会有一些重复计算在里面，我们和之前一样，本质还是在做暴力枚举，只是说枚举的个数变少了，我们能不能记录我们之前得到过的答案，通过牺牲空间换取时间呢，这里正是动态规划所要做的事情！


    

  • 问题拆解
    

    我们可以思考，如果我们从左到右，然后从上到下遍历矩阵，假设我们遍历到的当前位置是正方形的右下方的点，那其实我们可以看之前我们遍历过的点有没有可能和当前点组成符合条件的正方形，除了这个点以外，无非是要找另外三个点，这三个点分别在当前点的上方，左方，以及左上方，也就是从这个点往这三个方向去做延伸，具体延伸的距离是和其相邻的三个点中的状态有关
    

    • 

  • 状态定义
    

    因为我们考虑的是正方形的右下方的顶点，因此状态可以定义成 “当前点为正方形的右下方的顶点时，正方形的最大面积”
    

    • 

  • 递推方程
    

    有了状态，我们再来看看递推方程如何写，前面说到我们可以从当前点向三个方向延伸，我们看相邻的位置的状态，这里我们需要取三个方向的状态的最小值才能确保我们延伸的是全为 ‘1’ 的正方形，也就是
    

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

    • 

  • 实现
    

    在实现上，我们需要单独考虑两种情况，就是当前位置是 ‘1’，还有就是当前位置是 ‘0’，如果是 ‘0’ 的话，状态就是 0，表示不能组成正方形，如果是 ‘1’ 的话，我们也需要考虑位置，如果是第一行的元素，以及第一列的元素，表明该位置无法同时向三个方向延伸，状态直接给为 1 即可，其他情况就按我们上面得出的递推方程来计算当前状态。
    

    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
    public int maximalSquare(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int m = matrix.length, n = matrix[0].length;

        int[][] dp = new int[m][n];

        int maxLength = 0;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = matrix[i][j] == '1' ? 1 : 0;
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j], 
                                            Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    }

                    maxLength = Math.max(dp[i][j], maxLength);
                }
            }
        }

        return maxLength * maxLength;
    }
    

    • 



三角形最小路径和
题目描述
LeetCode 第 120 号问题：三角形最小路径和。


给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。


例如，给定三角形：


1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]


自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。


说明：


如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。


思考
给定一个三角形数组，需要求出从上到下的最小路径和，也和之前一样，按照四个步骤来分析：


    

  • 问题拆解：
    

    这里的总问题是求出最小的路径和，路径是这里的分析重点，路径是由一个个元素组成的，和之前爬楼梯那道题目类似，[i][j] 位置的元素，经过这个元素的路径肯定也会经过 [i - 1][j] 或者 [i - 1][j - 1]，因此经过一个元素的路径和可以通过这个元素上面的一个或者两个元素的路径和得到。
    

    • 

  • 状态定义
    

    状态的定义一般会和问题需要求解的答案联系在一起，这里其实有两种方式，一种是考虑路径从上到下，另外一种是考虑路径从下到上，因为元素的值是不变的，所以路径的方向不同也不会影响最后求得的路径和，如果是从上到下，你会发现，在考虑下面元素的时候，起始元素的路径只会从[i - 1][j] 获得，每行当中的最后一个元素的路径只会从 [i - 1][j - 1] 获得，中间二者都可，这样不太好实现，因此这里考虑从下到上的方式，状态的定义就变成了 “最后一行元素到当前元素的最小路径和”，对于 [0][0] 这个元素来说，最后状态表示的就是我们的最终答案。
    

    • 

  • 递推方程
    

    “状态定义” 中我们已经定义好了状态，递推方程就出来了
    

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

    • 

  • 实现
    

    这里初始化时，我们需要将最后一行的元素填入状态数组中，然后就是按照前面分析的策略，从下到上计算即可
    

    • 



代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[][] dp = new int[n][n];
    List<Integer> lastRow = triangle.get(n - 1);
    for (int i = 0; i < n; ++i) {
        dp[n - 1][i] = lastRow.get(i);
    }
    for (int i = n - 2; i >= 0; --i) {
        List<Integer> row = triangle.get(i);
        for (int j = 0; j < i + 1; ++j) {
            dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j);
        }
    }
    return dp[0][0];
}


最大子序和
题目描述
LeetCode 第 53 号问题：最大子序和。


给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。


示例:


1
2
3
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。


进阶:


如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。


思考
求最大子数组和，非常经典的一道题目，这道题目有很多种不同的做法，而且很多算法思想都可以在这道题目上面体现出来，比如动态规划、贪心、分治，还有一些技巧性的东西，比如前缀和数组，这里还是使用动态规划的思想来解题，套路还是之前的四步骤：


    

  • 问题拆解：
    

    问题的核心是子数组，子数组可以看作是一段区间，因此可以由起始点和终止点确定一个子数组，两个点中，我们先确定一个点，然后去找另一个点，比如说，如果我们确定一个子数组的截止元素在 i 这个位置，这个时候我们需要思考的问题是 “以 i 结尾的所有子数组中，和最大的是多少？”，然后我们去试着拆解，这里其实只有两种情况：
    

       i 这个位置的元素自成一个子数组;
    

       i 位置的元素的值 + 以 i - 1 结尾的所有子数组中的子数组和最大的值
    

    你可以看到，我们把第 i 个问题拆成了第 i - 1 个问题，之间的联系也变得清晰
    

    • 

  • 状态定义
    

    通过上面的分析，其实状态已经有了，dp[i] 就是 “以 i 结尾的所有子数组的最大值”
    

    • 

  • 递推方程
    

    拆解问题的时候也提到了，有两种情况，即当前元素自成一个子数组，另外可以考虑前一个状态的答案，于是就有了
    

    1
    dp[i] = Math.max(dp[i - 1] + array[i], array[i])
    

    化简一下就成了：
    

    1
    dp[i] = Math.max(dp[i - 1], 0) + array[i]
    

    • 

  • 实现
    

    题目要求子数组不能为空，因此一开始需要初始化，也就是 dp[0] = array[0]，保证最后答案的可靠性，另外我们需要用一个变量记录最后的答案，因为子数组有可能以数组中任意一个元素结尾
    

    • 



代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxSubArray(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    int result = dp[0];
    for (int i = 1; i < n; ++i) {
        dp[i] = Math.max(dp[i - 1], 0) + nums[i];
        result = Math.max(result, dp[i]);
    }
    return result;
}


总结
通过这几个简单的例子，相信你不难发现，解动态规划题目其实就是拆解问题，定义状态的过程，严格说来，动态规划并不是一个具体的算法，而是凌驾于算法之上的一种 思想。