Java 动态规划：经典路径问题详解 | 极客日志

Javajava算法

Java 动态规划：经典路径问题详解

基于 Java 语言讲解动态规划在路径问题中的应用，包含不同路径、带障碍路径、珠宝价值、下降路径及地下城游戏等题目。详细解析了状态定义、转移方程、初始化策略及填表顺序，并提供了完整代码示例。

PentesterX发布于 2026/3/30更新于 2026/4/130 浏览

Java 动态规划：经典路径问题详解

不同路径

LeetCode 题目链接

路径示意图

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

接着推导状态转移方程：要到达 i, j 位置有两种方式，要么从 i-1, j 向下达到，要么从 i, j-1 向右达到。将到达 i-1, j 和到达 i, j-1 的路径数相加即可得到到达 i, j 位置的方式数。即 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] 即可。

class Solution {
    public int uniquePaths(int m, int n) {
        // 建表
        int[][] dp = new int[m + 1][n + ];
        
         (   ; i <= m; i++) {
             (   ; j <= n; j++) {
                dp[i][j] = dp[i - ][j] + dp[i][j - ];
            }
        }
        
         dp[m][n];
    }
}

极客日志微信公众号二维码

更多推荐文章

相关免费在线工具

Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。在线工具，Keycode 信息在线工具，online
Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。在线工具，Escape 与 Native 编解码在线工具，online
JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。在线工具，JavaScript / HTML 格式化在线工具，online
JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。在线工具，JavaScript 压缩与混淆在线工具，online
加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online
Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

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] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return 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];
    }
}

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

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

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