动态规划解决网格路径问题：LeetCode 62题详解

1. 问题背景与核心挑战

第一次看到LeetCode 62题时，我被这个看似简单的网格路径问题难住了。题目要求计算从m×n网格的左上角到右下角的所有可能路径，每次只能向右或向下移动。作为动态规划(DP)的经典例题，它完美展现了如何将复杂问题分解为可管理的子问题。

在实际编程面试中，这类问题经常被用来考察候选人对DP思想的理解深度。我记得在2023年Google的面试题库中，这道题的变体出现了至少3次。不同于暴力解法可能面临的组合数爆炸（当m=n=20时，路径数已超过1.7×10^11），动态规划能以O(mn)的时间复杂度和空间复杂度优雅解决。

2. 动态规划解法原理拆解

2.1 状态定义与转移方程

定义dp[i][j]表示到达网格(i,j)位置的路径总数。关键观察点在于：

• 第一行和第一列的每个格子都只有1种到达方式（纯右移或纯下移）
• 其他位置的路径数等于上方格子路径数加左方格子路径数

这直接导出状态转移方程：

code复制dp[i][j] = dp[i-1][j] + dp[i][j-1]  (i>0且j>0)
dp[0][j] = 1
dp[i][0] = 1

2.2 空间优化技巧

原始解法需要O(mn)空间，但注意到每行计算只依赖上一行数据，可将空间优化到O(n)：

cpp复制vector<int> dp(n, 1);
for (int i = 1; i < m; ++i) {
    for (int j = 1; j < n; ++j) {
        dp[j] += dp[j-1];
    }
}

这个优化在面试中常被要求实现，特别是在处理大规模网格时（如m=n=10000）。

3. C++实现细节与边界处理

3.1 完整实现代码

cpp复制class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {