当前位置：首页 > article >正文

动态规划（二）——路径问题

article 2024/11/13 23:45:25

文章目录

路径问题
- 例题练习
- - 不同路径
  - 不同路径Ⅱ
  - 珠宝的最高价值
  - 下降路径最小和
  - 最小路径和
  - ★地下城游戏
- 总结

路径问题

动态规划题目解题过程回忆：

首先动态规划问题需要dp表（数组），这个表可能是一维的，也可能是二维的，可能是一个，也可能是多个。为了方便叙述，下面均使用dp[i]代表dp表的每一个元素。

状态表示

即dp[i]表示的状态或代表的含义，状态表示的确定一般有三个点：

题目要求
经验 + 题目要求
分析问题的过程中发现重复子问题

例如线性dp问题中，dp[i]的含义通常是：以xxx为结尾，xxx

状态转移方程

即求解dp[i] = ?（递推公式），通常考虑最近一个状态，看它怎样转化成此时的状态的，用公式表示出来（根据最近的一步，划分问题）

初始化

即将dp表中的某些元素提前初始化，避免利用状态转移方程填表时发生数组越界问题

填表顺序

保证填当前状态时，所需状态的值已经计算过

返回值

即问题的结果，需要结合经验与题目要求确定

dp问题编写代码的步骤：

创建dp表
初始化
填表
返回值
优化

几个优化：

空间优化——滚动数组

利用状态转移方程填表时，有时只需要前几个状态的值，除此之外的其他状态的值我们并不关心，此时就可以使用滚动数组的思想，即不需要创建一个完整的dp表，只需要创建几个变量存储填表时需要的几个状态值，这几个变量的值随着填表的过程不断改变，直到得到问题的解。

要使用滚动数组，必须明确填表时所需的状态值，且是一致的，比如填写dp[i]时都需要dp[i-1]；并且能够明确这几个值在填表过程中的变化规则，这一点通常是比较难确定的。

初始化优化——虚拟节点

虚拟节点的存在简化了初始化的逻辑，但这通常需要牺牲一些空间性能，即将dp表的规模扩大，增加一个空间或者几行几列等，并将这些额外空间的某些位置填上某些值，相关注意事项如下：

虚拟节点里面的值，要保证后面填表的结果是正确的
注意下标的映射关系，因为增加了虚拟节点，dp表的有效元素所处位置就会发生变化，如果题目中给出了某些集合，注意dp表与这些集合的下标映射关系

具体的使用在解题过程中体会理解

例题练习

不同路径

原题链接：62. 不同路径 - 力扣（LeetCode）
在这里插入图片描述

【分析】

这个问题显然是一道dp问题，因为这道题目包含大量的重复子问题（求到达右下角的所有路径，与到达任意一个位置的所有路径本质上是相同的），且整体问题的解由子问题的解组合而成。接下来就按照dp5步分析：

首先这道题目显然不是一道一维dp问题，我们需要创建一个二维的dp表：dp[m][n]

状态表示：按照线性dp的习惯，状态表示dp[i][j]表示到达[i][j]位置的所有路径
状态转移方程：根据题目：机器人只能向下或者向右走，再利用最近状态的思想，得到：一定是从上边或左边到达某个位置，即dp[i][j]与dp[i - 1][j]、dp[i][j - 1]有关，什么关系呢？

可以从上边向下到达，也可以从左边向右到达，有两种情况，因此dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，为什么不是dp[i][j] = dp[i - 1][j] + 1 + dp[i][j - 1] + 1呢？到达上边一个位置的方式有dp[i - 1][j]，到达指定位置只是走了一步，这一步是在到达上边的基础上，而不是一种方式。
初始化：根据状态转移方程，发现[i - 1]和[j - 1]可能越界，因此dp表需要初始化的位置是第一行和第一列，由于机器人只能向下或者向右走，因此初始化的值都是 1，即只有一种方式。
填表顺序：本题目需要保证填写某位置时，它的上边和左边都填写完毕，因此填表顺序为整体从上到下，每一行从左到右。
返回值：题目要求达到右下角的位置，因此返回值就是dp表的最右下角的位置：dp[m - 1][n - 1]

【代码实现】

class Solution {
    public int uniquePaths(int m, int n) {
        //创建dp表
        int[][] dp = new int[m][n];
        //初始化
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        //填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        //返回值
        return dp[m - 1][n - 1];
    }
}

我们发现，初始化的代码较为冗长，所以我们尝试使用虚拟结点的方式简化初始化，具体方案如下图：

在这里插入图片描述

我们将原dp表dp[m][n]增加了一行和一列，规模变为dp[m + 1][n + 1]，之后我们得考虑虚拟节点里面填写什么值才能保证填表时的正确性，即保证按照状态转移方程填写的实际数据区域的第一行和第一列的值都为1。最终确定了如上图的虚拟节点值，只需要dp[0][1]位置的虚拟节点填写1，其他位置都为0即可。

class Solution {
    public int uniquePaths(int m, int n) {
        //虚拟结点
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;

        //填表
        for(int i = 1; i < m + 1; i++) {
            for(int j = 1; j < n + 1; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        //返回值
        return dp[m][n];
    }
}

不同路径Ⅱ

原题链接：63. 不同路径 II - 力扣（LeetCode）

在这里插入图片描述

【分析】

这道题目和上一道题目是比较相似的，不同点就在于方法所给参数变为一个二维数组，二维数组中只会出现0或1两种值，1表示有障碍，0表示无障碍，机器人不能跨过障碍。

状态表示：dp[i][j]表示到达[i][j]位置时的不同路径数量
状态转移方程：状态转移方程的确定就是为了填表，那么填某一个元素时，如果该元素对应的位置有障碍物，此时该位置就不可能到达，dp[i][j] = 0；如果当前位置不是障碍物，此时就需要考虑最近一次状态了，依然可能从左边或上边到达，所以dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

注意：填写当前位置的元素时不需要考虑它的上边或左边是否是障碍物，因为如果是，那个位置的值dp[i][j] = 0，不会影响当前元素的填写。
初始化：需要初始化第一行和第一列，初始化时注意是否有障碍物，以第一行为例，从左向右初始化，只要有一个位置是障碍物，那么这个位置以及之后的位置的路径数量都应该是0。
填表顺序：从上往下，每一行从左往右
返回值：返回值是最右下角的元素

【虚拟结点】

虚拟节点简化初始化的方案和上一道题目一致，增加一行一列，然后为了保证后续填写元素的正确性，将dp[0][1]的值设置为1。

但是有所不同的是，这道题目采用虚拟节点方案时，需要考虑第二点注意事项：下标的映射关系。每次填表时，都需要先判断当前位置是否是障碍物，判断时需要找到题目所给的二维数组的对应位置，由于我们采用虚拟节点拓展了一行一列，因此dp[i][j] 对应的位置应该是obstacleGrid[i - 1][j - 1]，画图表示：

在这里插入图片描述

【代码实现】

//正常初始化
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //创建dp表
        int[][] dp = new int[m][n];
        //初始化
        dp[0][0] = obstacleGrid[0][0] == 1 ? 0 : 1;
        for(int i = 1; i < m; i++) {
            if(obstacleGrid[i][0] == 1) {
                dp[i][0] = 0;
            }else {
                dp[i][0] = (dp[i - 1][0] == 1 ? 1 : 0);
            }
        }
        for(int i = 1; i < n; i++) {
            if(obstacleGrid[0][i] == 1) {
                dp[0][i] = 0;
            }else {
                dp[0][i] = (dp[0][i - 1] == 1 ? 1 : 0);
            }
        }
        //填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        //返回值
        return dp[m -1][n - 1];
    }
}


//虚拟节点初始化
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        //虚拟节点初始化
        int[][] dp = new int[m + 1][n + 1];
        dp[0][1] = 1;
        //填表
        for(int i = 1;i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                //注意下标映射关系
                if(obstacleGrid[i - 1][j - 1] == 1) {
                    dp[i][j] = 0;
                }else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        //返回值
        return dp[m][n];
    }
}

珠宝的最高价值

原题链接：LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

在这里插入图片描述

【分析】

状态表示：根据做题经验以及问题确定状态表示dp[i][j]为到达[i][j]位置时可以拿到的珠宝的最高价值
状态转移方程：考虑最近一次的状态，拿到当前位置的珠宝前，我们一定先拿取了其上边或者左边的珠宝，具体拿谁取决于到达上边位置时珠宝的最高价值和到达左边位置时珠宝的最高价值，谁高就拿谁，然后拿当前位置的珠宝，最终得到的就是当前位置所能拿到的珠宝的最高价值：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j]
初始化：根据状态转移方程可知需要初始化第一行和第一列，

如果采用虚拟节点初始化，增加一行一列，值全为0（因为珠宝的价值均大于0）就可以，这样就能保证后续填表的正确性，同时注意下标映射关系。
填表顺序：从上往下填写每一行，每一行从左往右填写
返回值：返回右下角的元素

【代码实现】

//正常初始化
class Solution {
    public int jewelleryValue(int[][] frame) {
        //创建dp表
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m][n];
        //初始化
        dp[0][0] = frame[0][0];
        for(int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + frame[i][0];
        }
        for(int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + frame[0][i];
        }
        //填表
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];
            }
        }
        //返回值
        return dp[m - 1][n - 1];
    }
}


//虚拟节点初始化
class Solution {
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        //虚拟结点
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

下降路径最小和

原题链接：931. 下降路径最小和 - 力扣（LeetCode）

在这里插入图片描述

【分析】

状态表示：依旧根据问题确定状态表示（多加尝试，当前难度的题目大多都从问题入手），即到达[i][j]位置的下降路径最小和
状态转移方程：考虑最近的状态，想要到达当前位置，根据题目只能从上一行最近的三个位置到达，因为要求最小和，所以肯定是从三者值最小的位置向下走，然后加上此位置对应matrix数组的值，因此状态转移方程：dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i - 1], [j + 1])) + matrix[i][j]
初始化：怎样避免越界呢？我们直接采用虚拟节点的方式解决，本道题目可能越界的位置就是数组的第一行以及最左右两列，因此我们的虚拟节点扩容方案就如下图：

蓝色框框就是可能越界的位置，叉号叉起来的位置是实际不会越界访问到的位置，但为了方便定义，我们将dp表扩容到右边图的状态，即增加一行，增加两列。

确定了虚拟节点的位置，接下来就要确定虚拟节点中要预先填写哪些值了，dp表实际数据区域的第一行填写的值应当是题目所给数组第一行对应的值，因此为了避免影响到实际数据表第一行的结果，对虚拟节点第一行要初始化为0，此时要比较的三者的最小值总是0。然后是dp表实际数据区域最两侧的值，要保证虚拟节点的值不会影响到它们的值，我们必须保证一定不会选择从虚拟结点走下来，即虚拟节点的值不能是最小值，本道题目中-100 <= matrix[i][j] <= 100，因此两侧虚拟结点（不包括最上面一行）的值初始化为一个大于100的值即可，这样就能保证一定不会选到虚拟节点的值进而影响数据的正确性，初始化后：

别忘记下标的映射关系。
填表顺序：正确的填表顺序保证填写当前元素时，所需的其他状态的元素已经存在或填写完毕。本道题目填写时要求上一行最近的三个元素已经填写完毕，因此填表顺序从上往下，至于每一行的顺序就随意了。
返回值：返回最后一行最小的值

【代码实现】

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n + 1][n + 2];
        for(int i = 1; i < n + 1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }
        //填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
            }
        }
        //返回值
        return Arrays.stream(dp[n]).min().getAsInt();
    }
}

最小路径和

原题链接：64. 最小路径和 - 力扣（LeetCode）

在这里插入图片描述

【分析】

状态表示：根据经验 + 题目要求确定状态表示：到达[i][j]位置时的最小路径和
状态转移方程：根据最近的一步划分问题：某一位置，可能是从上边到达或从左边到达，具体从哪到达取决于到哪个位置的最小路径和较小，此时就不难得出状态转移方程：dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
初始化：初始化保证填表时不越界，需要初始化的位置是第一行第一列，以初始化第一行为例，某个位置（不包含dp[0][0]）的值等于前一个位置的值加上当前位置对应grid数组的值。

若采用虚拟节点，就需要加一行加一列，然后初始化某些虚拟节点的值，最终在填表时注意下标的映射关系：
填表顺序：从上往下填写每一行，每一行从左往右填写
返回值：返回右下角的值

【代码实现】

//正常初始化
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for(int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0]; 
        }
        for(int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }

        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]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}


//虚拟节点初始化
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 2; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for(int i = 2; i <= n; i++) {
            dp[0][i] = Integer.MAX_VALUE;
        }

        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]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
}

★地下城游戏

原题链接：174. 地下城游戏 - 力扣（LeetCode）

在这里插入图片描述

【错误分析】

第一步确定状态表示：按照以往的习惯，采用以[i][j]为结尾（到达[i][j]位置时）的所需的最低健康点数。

确定状态表示后，尝试推导状态转移方程：状态转移方程就是为了递推填表，所以我们可以先以题目所给例子尝试模拟一下整个过程：

首先可以确认的一点是填写当前位置时需要保证其上边和左边的元素已经填写完毕，为了避免越界，我们得先填写第一行的第一列的元素：

在这里插入图片描述

效果如上图，填写当前位置时如果碰到正数，即不会损失血量，所以填写的值一定是上一步的值。

初始化算是完成了，因此我们模拟填写剩下的元素：

在这里插入图片描述

当填写最后一个元素时，我们犯难了，因为最后一个位置是负数，而这个负数理应可以被前面的正数所抵消，这个正数不一定是上一步的正数，也有可能是更早的一步是正数，可以抵消，这时候，最后一个位置的-5理应能被从左边过来的正数全部抵消，此时最后一个位置是8；如果从上边过来，只能被1和3两个正数抵消4，也就是有1点溢出的伤害，此时为7，因此综合来看最后一个位置是7，看似没有问题，但实际上当前值dp[i][j]不仅取决于当前格子的值 dungeon[i][j]，还取决于从 [0][0] 到 [i][j] 的路径上的所有格子的值，因为很有可能需要某个格子的值抵消伤害。这就使得整个依赖关系十分复杂。（不同的路径可能导致不同的健康点数，这使得 dp[i][j] 的值不是一个确定的值，而是依赖于路径的选择）。

总结来说：采用这种状态表示会导致后效性问题，不仅体现在当前位置[i][j]要填写的元素受到从[0][0]到[i][j]路径上的所有元素的影响，也体现在当前位置的选择会影响后续的选择，因此这样的状态表示要考虑的东西很多，我们不妨换个思路。

【正确分析】

状态表示：既然以…为结尾，… 的思路不可行，那我们就尝试以…为起点，…，对应到这道题目，即：以[i][j]位置为起点到达结尾所需的最低健康点数。

既然状态表示如此，我们最终的返回值一定是：以[0][0]位置为起点到达结尾所需的最低健康点数，即左上角位置。对应的，整体的填表顺序应该也是从下往上，但填表顺序具体是怎样的，我们接着往下看。

因为每次只能往下或往右移动，所以当填写当前位置dp[i][j]时，它的最近的上一步肯定是下边dp[i + 1][j] 或右边dp[i][j + 1]，此时确定了状态转移方程的三个变量，接着按题目具体场景分析：状态转移方程 还需要哪些相关项？无非考虑两点：

dungeon数组的值。

右边或下边对应的dungeon数组的值会影响当前位置dp[i][j]的填写吗？显然不会，因为实际场景下，骑士是从左上角往右下角走，右边或下边是下一步的选择，当前还未到达，进而下一步的房间是扣血还是回血，数值是多少就与当前无关了。

因此，排除了两个无关项：dungeon[i + 1][j]和dungeon[i][j + 1]
dp表的值。

但dp表的值就有关了，前面我们分析过了，这道题目显然是从右边或下边选择一个作为路径的一部分，具体该选谁？

最近的上一步无非是：以右边位置[i][j + 1]或下边位置[i + 1][j]为起点到达结尾时所需的最低健康点数，此时与当前位置[i][j]无关，但如果我延伸到以[i][j]为起点，此时就相关了，我们得考虑dungeon[i][j]的值，如果是正数，则实际情况下骑士走到右边或下边所需要的最低血量就少了，因为可以抵消部分伤害，可抵消的血量dungeon[i][j](此处已经假设为正)有限，一定是选择所需最低健康点数较小的一个，即min(dp[i + 1][j], dp[i][j + 1])。

选择较小数后，还不能填入dp[i][j]，还得经过dungeon[i][j]，即：
- 如果dungeon[i][j]为正：可以抵消，有：min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
- 如果dungeon[i][j]为负：需要更高的所需最低健康点数，同样有：min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]（负负得正了，变为相加）
因此整个式子可以统一：min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]。

但这里还需要考虑一个特殊情况：当血包太大，即dungeon[i][j] > min(dp[i + 1][j], dp[i][j + 1])，此时会得到一个负数，表示在当前位置以负数开始也是可以的，但这不符合题目要求，当骑士的血量为非正数时，骑士就驾鹤西去了，不论如何，骑士最小的所需最低健康点数是1，因此当出现这种特殊情况，我们需要：max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])

讨论到这，状态转移方程就推导出来了：dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])

接下来讨论 初始化，根据状态转移方程思考填表时哪些位置可能出现越界访问？最后一行和最右边一列。

因此我们虚拟结点扩容方案如下图：

在这里插入图片描述

扩容完毕后，从虚拟节点的两点注意要求入手：

确定虚拟结点初始值，保证后续填表的正确性
- 首先确保右下角位置的值的正确性：填写是需要访问其右边和下边两个虚拟节点的值。怎样保证，这两个虚拟结点初始化什么值？
  
  这里的确定并没有什么可靠的推理，但可以根据一些线索猜到：纵观整个dp表，每个位置的值都大于等于1，即是一个正数，因此，我们得保证虚拟结点的值也是正数，我们尝试填入1这个特殊值，即：
  
  代入一些值就可以发现该方案可行。
- 接着确保其他位置值的正确性，这些位置只会访问到一个虚拟节点的值，还有一个真实数据，我们要确保每次都选择真实数据而不是虚拟结点的值，这需要回顾我们的选择依据：选择较小的。因此，我们将这些位置的虚拟节点初始化为+∞(Integer.MAX_VALUE)即可，这样就能保证虚拟节点的值不会被选择到，即：
注意下标的映射关系

因为虚拟节点都在右下角，所以dp表和dungeon数组的下标仍是一一对应的关系，只需要注意填表的起始位置即可。

填表顺序：从下往上填写每一行，每一行从右往左填写。

具体原因不再赘述。

返回值：即dp[0][0]。

【代码实现】

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        //虚拟结点
        int m = dungeon.length;
        int n = dungeon[0].length;

        //建表
        int[][] dp = new int[m + 1][n + 1];

        //虚拟节点初始化
        for(int i = 0; i < m - 1; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        for(int i = 0; i < n - 1; i++) {
            dp[m][i] = Integer.MAX_VALUE;
        }
        dp[m][n - 1] = dp[m - 1][n] = 1;

        //填表
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, (Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]));
            }
        }
        //返回值
        return dp[0][0];
    }
}

总结

总结一下动态规划中的路径问题：

整体做题思路还是5步，这样的话不会出现卡壳不知道该做什么的情况：

状态表示
状态转移方程
初始化
填表顺序
返回值

体会：

状态表示的确定尤为重要，要冷静分析当前的状态表示是否可行，如果当前状态表示使问题变得更复杂和不可控，要及时转变思路，如最后一道题目，不要死磕以……为结尾 的状态表示，放弃去尝试以……为起点的状态表示。
模拟填表时可行不意味着状态转移方程就能够写出来，如最后一道题目，采用某位置结尾的状态表示思路时，模拟的过程以及填表都比较顺利，但是确定状态转移方程时就犯难了，当前位置的值与整个路径上的值都有关，存在复杂依赖关系即后效性问题，此时问题就变得十分复杂，可能就需要换一个状态表示。
所有例题都采用了虚拟结点的方式，这是解决dp问题初始化的常用手段，一定要注意虚拟节点的两点注意事项，如果虚拟结点的初始值难以确定，就尝试一些特殊值，比如：+∞(Integer.MAX_VALUE)、-∞(Integer.MIN_VALUE)、最后一道题目的1等等。