每日算法 — 使用java实现网格路径：组合计数与动态规划路径搜索

问题引入

想象你站在一个 m × n 网格的左上角，目标是通过只能向右或向下移动的方式，到达右下角的终点。这是一个经典的组合计数问题，也是动态规划入门的最佳案例之一。本文将从数学组合公式与递推动态规划两个角度，用Java完整实现路径计数算法，并扩展到带障碍物的网格场景。

算法原理

方法一：组合数学

从左上角 (0, 0) 走到右下角 (m-1, n-1)，总共需要走 (m-1) 步向下和 (n-1) 步向右，总计 (m+n-2) 步。问题转化为：在这 (m+n-2) 步中选择哪些步向下（或向右），方案数为组合数：

C(m+n-2, m-1) = (m+n-2)! / [(m-1)! × (n-1)!]

直接计算阶乘容易溢出，需使用递推公式或动态规划计算组合数。

方法二：动态规划

设 dp[i][j] 表示从起点到达 (i, j) 的路径数。状态转移方程为：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

边界条件：dp[0][j] = 1（第一行只能向右），dp[i][0] = 1（第一列只能向下）。

扩展：带障碍物的不同路径II

若网格中存在障碍物（标记为 1），则障碍物格子的 dp 值为 0，其余转移逻辑不变。

Java完整实现

import java.util.Arrays;

/**
 * 网格路径计数算法实现
 * 包含组合数学、动态规划及带障碍物扩展三种解法
 */
public class GridPath {

    /**
     * 方法一：组合数学计算路径数
     * 时间复杂度 O(min(m,n))，空间复杂度 O(1)
     * 使用递推公式 C(a,b) = C(a,b-1) * (a-b+1) / b 避免溢出
     */
    public long uniquePathsMath(int m, int n) {
        // 确保 a >= b，减少计算量
        int a = m + n - 2;
        int b = Math.min(m - 1, n - 1);
        long result = 1;
        for (int i = 1; i <= b; i++) {
            result = result * (a - b + i) / i;
        }
        return result;
    }

    /**
     * 方法二：二维动态规划
     * 时间复杂度 O(m×n)，空间复杂度 O(m×n)
     */
    public int uniquePathsDP(int m, int n) {
        int[][] dp = new int[m][n];
        // 初始化第一列
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        // 初始化第一行
        for (int j = 0; j < n; j++) {
            dp[0][j] = 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];
    }

    /**
     * 方法三：滚动数组优化动态规划
     * 时间复杂度 O(m×n)，空间复杂度 O(n)
     * 只保留当前行和上一行的状态
     */
    public int uniquePathsOptimized(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 第一行所有列的路径数均为1
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1]; // dp[j]来自上方，dp[j-1]来自左方
            }
        }
        return dp[n - 1];
    }

    /**
     * 扩展：带障碍物的不同路径II
     * obstacleGrid[i][j] == 1 表示障碍物
     * 时间复杂度 O(m×n)，空间复杂度 O(n)
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        // 起点若为障碍物则直接返回0
        dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0; // 障碍物位置不可达
                } else if (j > 0) {
                    dp[j] += dp[j - 1]; // 累加左方路径数
                }
                // j==0时dp[0]保持原值（来自上方）
            }
        }
        return dp[n - 1];
    }

    /**
     * 打印网格路径的DP表格（调试用）
     */
    public void printDPTable(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 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];
            }
        }
        System.out.println("DP路径数表格 (" + m + "x" + n + "):");
        for (int i = 0; i < m; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
    }

    public static void main(String[] args) {
        GridPath solution = new GridPath();
        int m = 3, n = 7;

        System.out.println("=== 网格路径计数算法演示 ===");
        System.out.println("网格大小: " + m + " x " + n);
        System.out.println("组合数学结果: " + solution.uniquePathsMath(m, n));
        System.out.println("二维DP结果: " + solution.uniquePathsDP(m, n));
        System.out.println("滚动数组优化结果: " + solution.uniquePathsOptimized(m, n));

        solution.printDPTable(m, n);

        // 带障碍物测试
        int[][] obstacleGrid = {
            {0, 0, 0},
            {0, 1, 0},
            {0, 0, 0}
        };
        System.out.println("\n带障碍物路径数 (3x3, 中间有障碍): " 
            + solution.uniquePathsWithObstacles(obstacleGrid));
    }
}

复杂度分析

扩展思考

1. 路径输出：若需输出所有具体路径而非仅计数，可使用DFS回溯，配合StringBuilder记录路径方向。
2. 最小路径和：若网格中每个格子有权值，可改为记录最小/最大路径和，状态转移取 min(dp[i-1][j], dp[i][j-1]) + grid[i][j]。
3. 三维扩展：在三维网格中从 (0,0,0) 走到 (x,y,z)，只能沿正方向移动，方案数为 C(x+y+z, x) × C(y+z, y)。

网格路径问题是理解动态规划”最优子结构”与”无后效性”特性的绝佳入口，也是许多高级算法（如数字三角形、矩阵链乘）的思维基石。