动态规划5：不同路径问题与路径计数

引言

在动态规划系列的前四篇文章中，我们分别学习了爬楼梯问题、最长公共子序列、01背包问题和最长递增子序列。今天我们将探讨动态规划的另一个重要分支——路径计数问题。

路径计数问题是动态规划中非常重要的一类问题，它不仅在算法面试中频繁出现，还与组合数学紧密相关。通过学习这类问题，我们能够深入理解动态规划在计数问题中的应用。

问题背景

路径计数问题的核心思想是：在一个给定的空间中，计算从起点到终点的不同路径数量。这类问题通常具有以下特征：

• 方向限制：只能向特定方向移动（如向右、向下）
• 路径唯一性：每条路径由一系列移动步骤组成
• 计数目标：求所有可能路径的数量

经典例题一：不同路径

问题描述

LeetCode 62. 不同路径

一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

示例 1：
输入：m = 3, n = 7
输出：28

示例 2：
输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

解法一：动态规划

1. 状态定义

定义 dp[i][j] 表示：从起点 (0,0) 到达位置 (i,j) 的不同路径数量。

2. 状态转移方程

由于机器人只能向右或向下移动，到达位置 (i,j) 的路径只能来自：

• 从上方 (i-1,j) 向下移动
• 从左方 (i,j-1) 向右移动

因此状态转移方程为：

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

3. 边界条件

• dp[0][j] = 1：第一行只有一条路径（一直向右）
• dp[i][0] = 1：第一列只有一条路径（一直向下）

4. 代码实现

public int uniquePaths(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;
    }
    
    // 填充DP表
    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];
}

5. 空间优化

观察状态转移方程，dp[i][j] 只依赖于同一行的前一个元素和上一行的同一个元素，因此可以使用一维数组优化：

public int uniquePaths(int m, int n) {
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[j] = dp[j] + dp[j-1];
        }
    }
    
    return dp[n-1];
}

解法二：组合数学

数学分析

从 (0,0) 到 (m-1,n-1)，机器人需要：

• 向右移动 n-1 步
• 向下移动 m-1 步
• 总共移动 m+n-2 步

问题转化为：在 m+n-2 个位置中选择 m-1 个位置向下移动（或选择 n-1 个位置向右移动）。

这是一个组合数问题：C(m+n-2, m-1) 或 C(m+n-2, n-1)

代码实现

public int uniquePaths(int m, int n) {
    long result = 1;
    for (int i = 1; i <= Math.min(m-1, n-1); i++) {
        result = result * (m + n - 1 - i) / i;
    }
    return (int) result;
}

经典例题二：不同路径II（带障碍物）

问题描述（带障碍物）

LeetCode 63. 不同路径 II

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

示例：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

解法：动态规划（带障碍物）

状态转移方程（带障碍物）

如果 obstacleGrid[i][j] == 1：
    dp[i][j] = 0  // 有障碍物，无法到达
否则：
    dp[i][j] = dp[i-1][j] + dp[i][j-1]

代码实现（带障碍物）

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int m = obstacleGrid.length;
    int n = obstacleGrid[0].length;
    
    // 如果起点或终点有障碍物，直接返回0
    if (obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1) {
        return 0;
    }
    
    int[][] dp = new int[m][n];
    dp[0][0] = 1;
    
    // 初始化第一行
    for (int j = 1; j < n; j++) {
        dp[0][j] = (obstacleGrid[0][j] == 1) ? 0 : dp[0][j-1];
    }
    
    // 初始化第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = (obstacleGrid[i][0] == 1) ? 0 : dp[i-1][0];
    }
    
    // 填充DP表
    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];
}

空间优化版本

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    int n = obstacleGrid[0].length;
    int[] dp = new int[n];
    dp[0] = obstacleGrid[0][0] == 1 ? 0 : 1;
    
    for (int[] row : obstacleGrid) {
        for (int j = 0; j < n; j++) {
            if (row[j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j-1];
            }
        }
    }
    
    return dp[n-1];
}

经典例题三：最小路径和

问题描述（最小路径和）

LeetCode 64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

示例：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

解法：动态规划

状态定义

dp[i][j] 表示从 (0,0) 到 (i,j) 的最小路径和。

状态转移方程

dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

代码实现

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 j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j];
    }
    
    // 初始化第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0];
    }
    
    // 填充DP表
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);
        }
    }
    
    return dp[m-1][n-1];
}

原地修改版本（空间优化）

public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    
    // 初始化第一行
    for (int j = 1; j < n; j++) {
        grid[0][j] += grid[0][j-1];
    }
    
    // 初始化第一列
    for (int i = 1; i < m; i++) {
        grid[i][0] += grid[i-1][0];
    }
    
    // 填充网格
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }
    
    return grid[m-1][n-1];
}

路径计数问题的通用思路

1. 问题识别

路径计数问题通常具有以下特征：

• 在网格或图中寻找路径
• 移动方向有限制
• 需要计算路径数量或找到最优路径

2. 解题步骤

1. 状态定义：通常定义 dp[i][j] 表示到达位置 (i,j) 的某种最优值
2. 状态转移：根据可能的移动方向建立转移方程
3. 边界处理：初始化第一行和第一列
4. 空间优化：根据依赖关系优化空间复杂度

3. 常见变形

• 不同移动方向：四个方向、八个方向
• 带权重的路径：最小/最大路径和
• 路径记录：不仅求最优值，还要构造具体路径
• 多起点/终点：从多个起点到多个终点的路径

相关延伸问题

掌握了基本的路径计数问题后，可以尝试以下进阶题目：

1. LeetCode 120. 三角形最小路径和

   • 三角形结构的路径问题

2. LeetCode 931. 下降路径最小和

   • 可以斜向移动的路径问题

3. LeetCode 174. 地下城游戏

   • 带约束条件的路径问题

4. LeetCode 1301. 最大得分的路径数目

   • 路径计数与最优值结合

算法复杂度分析

时间复杂度

• 基本路径计数：O(m × n)
• 空间优化版本：O(m × n)

空间复杂度

• 二维DP：O(m × n)
• 一维DP优化：O(min(m, n))
• 原地修改：O(1)

总结

路径计数问题是动态规划的重要应用领域，它体现了DP在组合计数问题中的强大能力：

1. 状态设计简洁：通常以坐标作为状态维度
2. 转移逻辑清晰：基于移动方向的限制
3. 优化空间灵活：可以根据依赖关系进行空间优化
4. 应用场景广泛：从纯计数到最优化问题

通过掌握这类问题的解法，我们不仅学会了具体的算法技巧，更重要的是理解了动态规划在空间搜索问题中的应用模式。

系列文章回顾

• 动态规划入门：从爬楼梯问题开始
• 动态规划进阶：最长公共子序列问题
• 动态规划深入：01背包问题详解
• 动态规划4：最长递增子序列问题

推荐练习

• 在LeetCode上练习更多路径相关的DP问题
• 尝试实现带路径记录的版本
• 思考路径问题在实际项目中的应用场景