动态规划

什么是动态规划?

在了解动态规划前我们先了解一下记忆化搜索

假设我们要求斐波那契数列:

public static int count_2 = 0;
public int fibonacci(int n) {
        if (n <= 2) {
            count_2++;
            return n;
        }

        int f1 = 1;
        int f2 = 2;
        int sum = 0;
        for (int i = 3; i <= n; i++) {
            count_2++;
            sum = f1 + f2;
            f1 = f2;
            f2 = sum;
        }
        return sum;
    }

n为30时也不过计算二十几个数的累加,但是为什么采用递归竟然高达270万呢?

因为里面存在大量的重复计算,数越大,重复越多。例如当n=8的时候,我们看下面的结构图就已经有很多重复计算了

image-20240427222536278

如何优化呢?很简单,每一次将计算过的数存在数组,下一次在这个基础上计算就行

// 我们实现假定 arr 数组已经初始化好的了。
public static int[] arr = new int[50];
public static int count_3 = 0;
Arrays.fill(arr, -1);
arr[0] = 1;
int fibonacci(int n){
        if (n == 2 || n == 1) {
            count_3++;
            arr[n] = n;
            return n;
        }

        if (arr[n] != -1) {
            count_3++;
            return arr[n];
        } else {
            count_3++;
            arr[n] = fibonacci(n - 1) + fibonacci(n - 2);
            return arr[n];
        }
    }

路径专题

L62 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

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

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

示例 1:

img

输入:m = 3, n = 7
输出:28

示例 2:

输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3:

输入:m = 7, n = 3
输出:28

示例 4:

输入:m = 3, n = 3
输出:6

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 109

第一步:统计路径总数

这道题我们先自己直接求解:

class Solution {
    public static int uniquePaths(int m, int n) {
        return backTracking(1, 1, m, n);
    }

    static int backTracking(int m, int n, int ml, int nl) {
        if (m > ml || n > nl) {
            return 0;
        }
        if (m == ml && n == nl) {
            return 1;
        }
        return backTracking(m + 1, n, ml, nl) + backTracking(m, n + 1, ml, nl);
    }
}

答案是超时了,接下来我们优化分析过程:

从起点开始的每一个位置,要么向右,要么向下。每一种都将导致剩下的区间的减少了一行或者一列,形成两个不同的区间。如图:

image-20240427225223830

用一个更简单的例子:

image-20240427225243905

  1. 如果向右走,也就是图1的情况,后面是一个3x1的矩阵,此时起点下面的两个灰色位置就不会再访问了,只能从绿色位置一直向下走,只有一种路径。
  2. 如果是向下走,我们可以看到原始起点右侧的就不能再访问了,而剩下的又是一个2X2的矩阵,也就是从图中绿色位置到红色位置,此时仍然可以选择向右或者向下,一共有两种路径。

所以上面的情况加起来就是一共有3种。

而3*3时:

image-20240427225539114

可以看到,一个3X3的矩阵下一步就变成了一个3X2或者2X3的矩阵,而总路径数,也是是两者各自的路径之和。

上面这个过程,我们也可以用二叉树表示出来:

image-20240427225749971

相当于反向求解,代码:

public static int uniquePaths(int m, int n) {
        return backTracking(m, n);
    }

    static int backTracking(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return backTracking(m - 1, n) + backTracking(m, n -1);
    }

第二步:使用二位数组优化递归

我们来优化递归的问题,研究如何结合二维数组来实现记忆化搜索。

从上面这个树也可以看到在递归的过程中存在重复计算的情况,例如{1,1}出现了两次,如果是一个N*N的空间,那{1,0}和{0,1}的后续计算也是一样的。

在位置(1,1)处,不管从(0,1)还是(1,0)到来,接下来都会产生2种走法,因此不必每次都重新遍历才得到结果。

image-20240429120237697

为此,我们可以采取一个二维数组来进行记忆化搜索,算好的就记录在数组中,也就是这样子:

image-20240429120249255

每个格子的数字表示从起点开始到达当前位置有几种方式,这样我们计算总路径的时候可以先查一下二维数组有没有记录,如果有记录就直接读,没有再计算,这样就可以大量避免重复计算,这就是记忆化搜索。

根据上面的分析,我们可以得到两个规律:

  1. 第一行和第一列都是1。
  2. 其他格子的值是其左侧和上方格子之和。

对于其他m,n的格子,该结论一样适用的,例如:

image-20240429120455650

公式来表示:

image-20240429120638392

得到代码如下:

public int uniquePaths(int m, int n) {
    int[][] f = new int[m][n];
    f[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
         if (i > 0 && j > 0) {
               f[i][j] = f[i - 1][j] + f[i][j - 1];
            } else if (i > 0) {
                f[i][j] = f[i - 1][j];
            } else if (j > 0) {
                f[i][j] = f[i][j - 1];
             }
         }
    }
    return f[m - 1][n - 1];
}

第三步:滚动数组将二维数组转换为一维数组

二维数组占用空间较大,我们这里继续看上面的图,在上图中除了第一行和第一列都是1外,每个位置都是其左侧和上访的格子之和,那我可以用一个大小为n的一维数组解决来:

  1. 遍历数组,将一维数组所有元素赋值为1

image-20240429125151416

  1. 再次从头遍历数组,除了第一个,后面每个位置是其原始值和前一个位置之和,也就是这样

image-20240429125214011

  1. 重复第二步:除了第一个,后面每个位置仍然是其原始值和前一个位置对应数的和,也就是这样

image-20240429125230070

这样刚好可以完成公式的计算

继续循环,题目给的m是几就循环几次,要得到结果,输出最后一个位置的15就可以了。

上面这几个一维数组拼接起来,是不是发现和上面的二维数组完全一样的?而这里我们使用了一个一维数组就解决了,这种反复更新数组的策略就是滚动数组.

而公式也得到:dp[j] = dp[j] + dp[j - 1]

代码如下:

public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for(int i = 1; i < m; ++i) {
            for(int j = 1; j < n; ++j) {
                //等式右边的 dp[j]是上一次计算后的,加上左边的dp[j-1]即为当前结果
                dp[j] = dp[j] + dp[j - 1];
            }
        }
        return dp[n - 1];
    }

注:这里题目给定的m和n分别是长和宽

L64 最小路径和

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

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

示例 1:

img

输入: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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200

由于题目限定了我们只能「往下」或者「往右」移动,因此我们按照当前位置可由哪些位置转移过来 进行分析:

  • 当前位置只能通过「往下」移动而来,即有f[i][j] = f[i-1][j] + grid[i][j]
  • 当前位置只能通过「往右」移动而来,即有 f[i][j] = f[i][j-1] + grid[i][j]
  • 当前位置既能通过「往下」也能「往右」移动,即有f[i][j] = min(f[i][j-1],f[i-1][j]) + grid[i][j]

二维数组的更新过程:

image-20240429163141772

状态:

状态就是下面表格更新到最后的二维数组,而通过前面格子计算后面格子的公式就叫状态转移方程

令f[i][j]表示从f(0,0)走到格子(i,j)的路径的最小数字总和,则使用表达式来表示上面的关系就是

image-20240429163312195

代码实现:

public int minPathSum(int[][] grid) {        
        int m = grid.length, n = grid[0].length;
        int[][] f = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 && j == 0) {
                    f[i][j] = grid[i][j];
                } else {
              int top  = i - 1 >= 0 ? f[i - 1][j] + grid[i][j] : Integer.MAX_VALUE;
              int left = j - 1 >= 0 ? f[i][j - 1] + grid[i][j] : Integer.MAX_VALUE;
                    f[i][j] = Math.min(top, left);
                }
            }
        }
        return f[m - 1][n - 1];
    }

L120 三角形最小路径和

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 ii + 1

示例 1:

输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

示例 2:

输入:triangle = [[-10]]
输出:-10

提示:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -104 <= triangle[i][j] <= 104

在看解析之前,我们先看一下这个题是什么意思。本题就是1.2中最小路径和的简单变换,
为了方便处理,我们可以先处理成对角线结构。

image-20240429171252967

这里我们需要知道,像5这种地方,我们需要计算的是3和4,都需要计算一遍取的是最小值,还有11,18

这里我们理解一个新概念:

无后性

确定一道题目是否可以用 DP 解决,要从有无后效性进行分析

所谓无后效性就是我们转移某个状态需要用到某个值,但是并不关心该值是如何而来的

或者说:当前某个状态确定后,之后的状态转移与之前的决策无关,因此我们可以确定使用 DP 进行求解

拿这道题举例来说:最后一行的某个位置的值,根据题意只能从上一行的某一个位置或者某两个位置之一转移而来。

我们只关注前一位的累加值是多少,特别是最小累加值是多少,而不关心这个累加值结果是由什么路径而来的,这就满足了「无后效性」的定义。

理解动态规划

DP能解决哪类问题?

直观上,DP一般是让找最值的,例如最长公共子序列等等,但是最关键的是DP问题的子问题不是相互独立的,如果递归分解直接分解会导致重复计算指数级增长(想想前面的热身题)。而DP最大的价值是为了消除冗余,加速计算

有无后效性

例如上面第一道路径题,有两种问法:哪个是DP?

A 求有多少种走法 B 输出所有的走法

我们说动态规划是无后向型的,只记录数量,不管怎么来的,因此A是DP问题,而B不能用DP。如果你理解上一章回溯的原理的话,就知道回溯可以记录所有的路径,因此B是个回溯的问题。

区别

  • 回溯:能解决,但是解决效率不高
  • DP:计算效率高,但是不能找到满足要求的路径。

动态规划只关心当前结果是什么,怎么来的就不管了,所以动态规划无法获得完整的路径,这与回溯不一样,回溯能够获得一条甚至所有满足要求的完整路径。

  1. DP的基本思想是将待求解问题分解成若干个子问题,先求子问题,再从这些子问题中得到原问题的解。

  2. 接下来,既然穷举,那为啥还要有DP的概念?这是因为穷举过程中存在大量重复计算,效率低下,所以我们要使用记忆化搜索等方式来消除不必要的计算,所谓的记忆化搜索就是将已经计算好的结果先存在数组里,后面直接读就不再重复计算了。

  3. 因为DP问题一定具备“最优子结构”,这样才能让记忆时得到准确的结果。至于什么是最优子结构,我们还是要等后面具体问题再看。

  4. 有了最优子结构之后,我们还要写出正确的“状态转移方程”,才能正确的穷举。也就是递归关系,但是在DP里,大部分递推都可以通过数组实现,因此看待的代码结构一般是这样的for循环,这就是DP代码的基本模板:

//   初始化base case,也就是刚开始的几种场景 ,有几种枚举几种
        dp[0][0][...]=base case
    //  进行状态转移
        for 状态1 状态1的所有取值
            for 状态2 in 状态2的所有取值
               for ....
                 dp[状态1][状态2][...]=求最值Max(选择1,选择2,...)
    }

一般说来,动态规划题目有以下三种基本的类型:

  1. 计数有关,例如求有多少种方式走到右下角,有多少种方式选出K个数使得***等等,而不关心具体路径是什么。
  2. 求最大最小值,最多最少等等,例如最大数字和、最长上升子序列长度、最长公共子序列、最长回文序列等等。
  3. 求存在性,例如取石子游戏,先手是否必胜;能不能选出K个数使得**等等。
  • 第一步:确定状态和子问题,也就是枚举出某个位置所有的可能性,对于DP,大部分题目分析最后一步更容易一些,得到递推关系,同时将问题转换为子问题。
  • 第二步:确定状态转移方程,也就是数组要存储什么内容。很多时候状态确定之后,状态转移方程也就确定了,因此我们也可以将第一二步作为一个步骤。
  • 第三步:确定初始条件和边界情况,注意细心,尽力考虑周全。
  • 第四步:按照从小到大的顺序计算:f[0]、f[1]、f[2]...

我们要自始至终,都要在大脑里装一个数组(可能是一维,也可能是二维),要看这个数组每个元素表示的含义是什么(也就是状态),要看每个数组位置是根据谁来算的(状态转移方程),然后就是从小到大挨着将数组填满(从小到大计算,实现记忆化搜索),最后看哪个位置是我们想要的结果。