算法【Java】—— 动态规划之路径问题

前言

本文章终点解析第一道题目【不同路径】和最后一道题目【地下城游戏】的动态规划思路，中间几道题目会很快过完，大家如果不熟悉动态规划的思路可以重点看一下这两道题目的解析。

不同路径

https://leetcode.cn/problems/unique-paths

解析：
首先确定状态表示：根据经验和题目要求，我们将 dp[i][j] 表示为达到 i j 位置一共有多少条路径。

接着推导状态转移方程：首先要到达 i, j 位置一共有两种方式，要么从 i-1,j 向下达到，要么从 i, j-1 向右达到。
我们将达到 i-1, j 和 达到 i , j-1 一共有多少条路径进行相加就可以得到 到达 i, j 位置 一共有多少种方式了。那么如何获得 达到 i-1, j 和 达到 i , j-1 一共有多少条路径？这不就是我们的状态表示吗，即 dp[i-1][j] 和 dp[i][j-1]
所以状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]

现在来进行初始化，为了方便我们填表不发生越界，我们决定多开一列和一行：

蓝色区域是我们要多开的空间，为什么开的是左边和上面的空间，因为我们的状态转移方程要用到上面和做左边的状态数值，为了避免在求原数组第一行和第一列发生越界，我们就多开了这部分空间，如果你不开，你就要在填表之前把第一行和第一列给提前填好。

初始化还要注意填表的正确性，因为我们多开的空间是会影响到第一行和第一列的状态数值的，我们必须保证第一行和第一列是正确的状态数值。

第一个状态数值应该为多少？状态表示是到达某个位置一共有多少条路径，那么达到第一个位置应该是一条路径，所以要确保dp[1][1] = 1 的话，我们只需要 dp[0][1] 或者 dp[1][0] 其中一个等于 1 即可，其他全部初始化为0，就可以确保我们的第一行和第一列的正确性。

接下来是填表顺序：因为我们的状态转移方程是需要上一个和左边一个的状态值，所以我们需要先把左边和上面的状态值填完，也就是说填表顺序应该为 从上到下，从左到右。

最后就是返回值，因为题目要求到达终点一共有多少条路径，我们直接返回 dp[m][n] 即可，也就是 dp 表的最后一个位置。

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; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        //返回值
        return dp[m][n];
    }
}

不同路径Ⅱ

https://leetcode.cn/problems/unique-paths-ii

解析：
状态表示：达到 某一个位置一共有多少条路径

状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]

初始化：因为要用到左边和上边的状态数值，所以上面多开一行，右边多开一列，然后dp[0][1] 或者 dp[1][0] 其中一个设置为 1 ，保证填表的正确性。

填表顺序：从上往下，从左往右

返回值：dp[m][n]

细节处理：因为我们不能通过障碍物，所以遇到障碍物的状态值应该写 0， 不需要状态转移方程来推到其状态值

class Solution {
    public int uniquePathsWithObstacles(int[][] ob) {
        //构建 dp 表
        int m = ob.length;
        int n = ob[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(ob[i-1][j-1] != 1) {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        //返回值
        return dp[m][n];
    }
}

珠宝的最高价值

https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof

解析：
状态表示：到达某一个位置能获得的珠宝的最大价值

状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + jewelleryValue[i][j]

初始化，为了填表方便，多开空间。
要保证第一行和第一列的正确性，我们只要保证 dp 表的初始状态值为 0 即可，也就不需要什么额外处理了。
注意下标，因为我们多开了空间，如果要访问原数组必须你的 i, j 应该都减去 1，即 jewelleryValue[i-1][j-1]

填表顺序：从上到下，从左到右

返回值：dp[m][n]

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];
    }
}

下降路径最小和

https://leetcode.cn/problems/minimum-falling-path-sum

解析：
状态表示：到达某个位置的路径最小和设为状态值

状态转移方程：要求出某一个位置的状态值，需要利用上面和对角线的左边与右边的状态值。dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j-1]) + 该位置在原数组的数值。

初始化，因为我们要利用三个状态值，为了避免越界，所以我们多开三个空间，左边一列，上面一行，右边一列：

为了确保全表正确，也就是不能让多开的空间影响到我们的状态值，所以最上面一行设置为 0，左边一列和右边一列设置为 Integer.MAX_VALUE

填表顺序：上到下，左到右

返回值，遍历最后一行获得最小值然后返回即可。

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

最小路径和

https://leetcode.cn/problems/minimum-path-sum

解析：
状态表示：到达某一个位置的路径最小和

状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 该位置在原数组的数值

初始化：多开上面一行和左边一列的空间，为了保证填表的正确性，多开的空间先全部设置为 Integer.MAX_VALUE，然后将 dp[0][1] 或者 dp[1][0] 设置为 0 即可。

填表顺序：从上到下，从左到右

返回值：dp[m][n]

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 = 0; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        Arrays.fill(dp[0], Integer.MAX_VALUE);
        dp[0][1] = 0;
        //填表
        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];
    }
}

地下城游戏

https://leetcode.cn/problems/dungeon-game

解析：
状态表示：到达某一个位置时所需要的最低血量，这个状态表示是不能推导出状态转移方程的，假设你硬推，大概率是推出 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 原数组对应的数值。可是这个方程是错误的，因为你到了 i, j 这个位置得到的最低血量可能不能支撑后面的前进，所以你的状态转移方程还需要考虑后面的情况，可是你考虑不到了，因为后面的状态值根本就还没填你是无法获取的，因此这个状态表示是不可行的。

那么我们就要另辟蹊径了，状态表示除了以某个位置结尾还可以以某个位置为起点，那么我们现在使用以某个位置为起点的形式来看看能不能推导出来。

那么新的状态表示应该为 从某一个位置出发所需要的最低血量。

状态转移方程：要想获得 dp[i][j] 就要知道右边和下面所需要的最低血量，求出其中的最小值，而右边和下面所需要的最低血量正好对应我们的状态表示，即右边的最低血量为 dp[i][j+1] ，下面的最低血量为 dp[i+1][j]，那么状态转移方程为 dp[i][j] = min(dp[i+1][j]，dp[i][j+1]) - 原数组对应的数值。这方程是这样推导的：首先该位置的最低血量 + 原数组对应的数值 要等于到往下一个位置的 最低血量，然后移项就可以得到上面的状态转移方程

这里还有一个细节：如果原数组是一个血包，也就是一个正数，是有可能让我们的 状态值推导为 小于等于 0 的，这个状态值骑士都死了，还救什么公主，所以这种情况我们要判断如果是则直接设置为 1。

初始化：因为我们的状态推导需要用到右边和下边的状态值，所以为了避免越界和方便填表，我们下面多开一行，右边多开一列。然后就是要保证填表的正确性，也就是保证我们右边和下面的状态值不因为多开的空间而发生错误。首先先来考虑右下角：

首先要明确绿色的框框是我们救出公主后达到这里多需要的最低血量，应该为 1， 因为骑士的血量不能为0也不能为负值否则就直接死亡了，死了根本就道理绿色区域。

剩余蓝色的区域我们应该设置为 Integer.MAX_VALUE，避免蓝色区域影响到我们的填表正确性。

填表顺序：根据状态转移方程，我们需要先知道右边和下面的状态值才能进行推导，所以从下到上，从右到左进行填表。

返回值：从左上角到右下角所需要的最低血量，返回 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; i++) {
            dp[i][n] = Integer.MAX_VALUE;
        }
        Arrays.fill(dp[m], Integer.MAX_VALUE);
        dp[m-1][n] = dp[m][n-1] = 1;
        //填表
        for(int i = m - 1; i >= 0; i--) {
            for(int j = n - 1; j >= 0; j--) {
                dp[i][j] = Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
                if(dp[i][j] <= 0) 
                    dp[i][j] = 1;
            }
        }
        //返回值
        return dp[0][0];
    }
}