数据结构与算法

发布日期: 2022-11-02

1. 最优子结构详解

最优子结构是某些问题的一种特定性质,但是能否使用动态规范的区分点是其具有最优子结构但是不具有重叠子问题。遇到了最优子结构失效的情况下,一个好的策略是改造问题。

最优子结构失效的例子

目前已经知道每个班内的最大分数差,问你能否求出全校的最大分数差?

这是不能够求出来的。首先我们分析:我们不能够通过每个班的最优值推出全校的最优值,这是因为全校的最大分数差可能出现在两个班之中,那么这就出现了一种什么样的情形呢?

在这种情况下,子问题的划分并不合理,是将一些合法的子问题给漏掉了,那么漏掉的这些问题该如何得到呢?一种手段是通过两个或者以上不同的状态来获取得到一种手段是通过两个或者以上不同的选择来得到,当然,如果能可行的话也能得到最优解,但是这并不是符合我们定义的最佳定义。

如何改造问题?

对于前面失效的例子,发现我们定义的子问题形式不合理,从而导致子问题之间不相互独立,这时候的一个办法就是进行问题的重新定义,从而获取一个新的子问题的定义,从而满足条件。

上面的问题先写一个暴力解

int result = 0 ;
//对于每一个班的学生
for(int i = 0;i<n;i++){
    for(int j = i;j<i;j++){
        if(a[i] - a[j] > max){
            max = (a[i]-a[j]);
        }
    }
}
cout<<max<<endl;

改造问题,也就是将问题进行等价化,这时候需要对问题进行重新分析:最大分数差=>学生间的最大分数差=>最高分的学生与最低分的学生的成绩的差值,这样的话我们就重新划分了子问题,从而使得子问题对于总问题而言是相互独立的,也就是每一次的状态转移只依赖于一个子问题的结果,这是我们写出状态转移的前提条件。

扩展:

如何求二叉树的最值?(假设树上的节点都是非负数)

int maxVal(TreeNode root){
    if(root == null){
        return -1;
    }
    //接下来的抛给递归
    int left = maxVal(root.left);
    int right = maxVal(root.right);
    return Math.max(left,right);
}

这个问题也具有最优子结构的性质,分析:以根节点出发的树上的最大值=>左子树上的最大值与右子树上的最大值两者取最大，每次状态转移只需要依赖于一个子问题,因此满足最优子结构。

也许你会问为什么说只需要依赖于一个子问题?

明明看到了是需要依据两个子问题的结果才能进行状态转移呀,怎么解释?

首先我们需要明确的是,所谓依赖于一个子问题的结果,指的是对于下一次状态转移,是根据某个选择的结果来转移的。上述的例子,最终的最大值只依赖于能够取到最值的那根子树,是依据这个单个结果进行转移的,因此我们说这个问题是独立的子问题。

而对于前面的求学校里面的最大分数差,如果要求出答案,必须通过某种手段(可能做不到,因为定义不合理)来使得多个子问题联合在一起,根据这些多个子问题的共同结果进行下一次转移。

这就是最核心的问题所在。

2. 重叠子问题

2.1 题目引入

现在给你输入一个二维数组 grid，其中的元素都是非负整数，现在你站在左上角，只能向右或者向下移动，需要到达右下角。现在请你计算，经过的路径和最小是多少？

一般来说,让你在二维矩阵中求最优化问题(最大值或者最小值),组合是递归+备忘录

如果我们想要从D走到B,我们可以这样反推:

那么必经之路是A或者是C(因为题目要求说我们只能够向右或者向下走)

那么问题规模就转化成了从D走到A的最小路径和和从D走到C的最小路径和的最小值取最小。

而对于走到A或者走到C的这两条路径的最小路径和,又可以这样反推过去。

这个过程就是在不断分解子问题,回到一个base-case的过程。

我们从动态规划的基本思路来分析这个问题

定义状态:状态就是不断变化的量,从起点走到终点这个过程中,不断变化的量是从起点出发去试探的终点,比如说上图的终点B,那么状态就是从起点到A或者从起点到C这个状态。
定义选择:选择就是在当前的格子,选择向下走还是选择向上走
定义dp函数

//表示从(0,0)走向(i,j)的最小路径和
int dp(int[][] grid,int i,int j){}

定义base-case

当从(0,0)走向(0,0)的时候,路径和就是grid[0][0]

定义状态转移方程

从(i,j)向右走(i,j+1),向下走(i+1,j)

那么如果我们是递归的,那么就是从上一次的选择到这一次的状态

上一次我可能是在左边,可能是在上边,那么对应的下标就是(i,j-1),(i-1,j)

private int[][] memo;
public int minPathSum(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    memo = new int[n][m];
    return dp(grid,n-1,m-1,n,m);
}
private int dp(int[][] grid,int i,int j,int n,int m){
    if(i == 0&&j ==0){
        return grid[0][0];
    }
    if(i<0 || j< 0 || i>=n || j>=m){
        return Integer.MAX_VALUE;
    }
    if(memo[i][j] != 0){
        return memo[i][j];
    }
    //做出选择
    memo[i][j] = Math.min(dp(grid,i-1,j,n,m),dp(grid,i,j-1,n,m))+grid[i][j];
    return memo[i][j];
}

以上是自顶向上的做法,接下来采用自底向下的解法

public int minPathSum(int[][] grid) {
    int n = grid.length;int m = grid[0].length;
    int dp[][] = new int[n][m];
    //base-case
    dp[0][0] = grid[0][0];
    for(int i = 1;i<n;i++){
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    for(int j = 1;j<m;j++){
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    for(int i = 1;i<n;i++){
        for(int j = 1;j<m;j++){
            dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
        }
    }
    return dp[n-1][m-1];
}

2.2 题目分析

在一开始中的递归算法中,如果我们没有做一个备忘录的记录,那么就会产生重叠子问题,如:

同时也可以通过代码不难看出其具有重叠子问题

dp(grid,i-1,j);
dp(grid,i,j-1);

可以看到i和j的值在不断减小,如果想从(i,j)转移到状态(i-1,j-1),那么路径就会有

(i,j)->(i-1,j)->(i-1,j-1)
(i,j)->(i-1,j-1)->(i-1,j-1)

能写得出来两条路径,这说明(i-1,j-1)会被多次计算,因此存在重叠子问题。

问题:你如何知道这是重叠子问题而不是路径的穷举?

就是说,想法是从(i,j)到(i-1,j-1)这两条路径,如果是穷举的思路的话,那么肯定就是枚举这两条路径的值,从而得到最小值,那么提前剪枝会不会导致我们漏掉答案了呢?

有这种想法是因为没有深刻理解递归的过程,我们的递归是从base-case(0,0)开始的,从(0,0)做选择,我们的Math.min()能够确保得到一个最优子结构,然后根据此最优子结构去推导后面的递归过程,因为我们能够得到一个最优解,因此在之前穷举的路径上,有些路径是不必要的穷举,因此直接剪枝是合理的。

说人话就是,我这玩意都已经算过了,你还去算它干啥?

例如:

(0,0)<-(1,0)<-(1,1)<-(1,2)<-(2,2)

(0,0)<-(0,1)<-(1,1)<-(2,1)<-(2,2)

来看看从(0,0)到(2,2)的过程,在计算,其必经之路是(1,1),我们在走第一条路径的时候就会走一次:

这是必要的,因为我们并不知道哪条路径最短

(0,0)<-(1,0)<-(1,1)

(0,0)<-(0,1)<-(1,1)

然后走第二条路径:我们发现,如果没有备忘录,那么之前计算出来的从(0,0)到(1,1)的最短路就用不上了，它会再去走一遍这条路,找看从(0,0)到(1,1)到底是途径(1,0)最短还是(0,1)最短

就会再算一次,这就导致了重叠子问题!

3.dp数组的大小设置

关于dp数组的定义,有的数组会被初始化为dp[n+1][m+1]有的会被初始化为dp[n][m],理论上怎么定义都可以,其中一个关键是你的base-case应该要怎么定义。

一些经典的dp问题中,例如字符串相关问题,我们需要定义base-case,这时候就需要设定一个占位符表示空串,这时候就需要有一位偏移位了,而有一些问题不需要有空串之类的特殊情况,它的内置情况就是base-case了,这时候就不需要有偏移,比如说上文的最小路径和

4.dp数组的遍历方向

关于dp数组的遍历方向

在遍历的过程中,所需的状态必须是已经计算出来的
遍历结束之后,存储的结果的那根位置必须已经被计算出来。

5. base-case的初始化以及备忘录的初始化

输入一个n*n的二维数组matrix,请你计算从第一行落到最后一行,经过的路径和最小为多少,就是说你可以站在matrix的第一行的任意一个元素,需要下降到最后一行。

每次下降,可以向下,向左下,向右下三个方向移动一格,也就是说,可以从matrix[i][j]降到matrix[i+1][j]或者amatrix[i+1][j+1]这三个位置

这道题的话,如果我们想要穷举答案,那么就是穷举所有的起点和所有的终点,第一行有n个点,最后一行为n个点，那么一共就是n*n个组合。

还有一种想法就是自底向上分析,我们从终点出发,终点向上走,每次三个选择,每次选择最小的那个,直到到达起点,这样的路径就是最优的,这样的话不需要穷举所有的组合了。

可以先写出一个dp分析函数

class Solution {
    private int[][] memo;
    private int dp(int[][] matrix,int i,int j,int n,int m){
        if(i < 0 || j < 0 || i >= n|| j >= m){
            //表示该路径不可达
            return Integer.MAX_VALUE;
        }
        //base-case
        if(i == 0){//回到最上层
            return matrix[0][j];
        }
        if(memo[i][j] != Integer.MAX_VALUE){
            return memo[i][j];
        }
        //状态转移
        memo[i][j] =  matrix[i][j]+Math.min(
                Math.min(dp(matrix,i-1,j,n,m),
                         dp(matrix,i-1,j-1,n,m)),
                         dp(matrix,i-1,j+1,n,m));
        return memo[i][j];
    }
}

需要探讨三个问题

对于索引的合法性检测,返回值为什么是MAX_VALUE?其他的值行不行?

对于索引

i < 0 || j < 0 || i >= n|| j >= m

这个下标会导致越界,但是我们希望它返回的值不会影响到我们的答案推算,因此返回值应该要设置成一个无法被计入答案的数值。我们通过题目的案例1<=n<=100,-100<=matrix[i][j]<=100那么答案的合法区间就是[-10000,10000],那么只要我们选取的值在这个区间之外即可。

(-inf, -10001] U [10001, +inf)