LeetCode动态规划经典题：Unique Paths 网格路径计数详解
这道题是典型的动态规划入门题，非常适合练习二维 DP 的建模思路。leetcode+1
题目概述
在一个 m×n 的网格上，有一个机器人从左上角 (0,0) 出发，只能向右或向下移动一步。leetcode
目标是到达右下角 (m−1,n−1)，要求计算一共有多少条不同的路径。leetcode
约束：1≤m,n≤100，测试数据保证答案不超过 2×10^9。leetcode
动态规划建模
状态定义：令 dp[i][j] 表示从起点 (0,0) 走到格子 (i,j) 的不同路径数量。leetcode
状态含义：每个格子只可能从上方 (i-1,j) 或左方 (i,j-1) 走到，因此到达当前格子的路径数等于来自这两个方向路径数之和。leetcode+1
状态初始化
起点：dp[0][0] = 1，表示机器人一开始就在这个格子上，只有 1 种方式"到达"自己。leetcode
第一行：对于 i = 0, j > 0，由于只能向右走，所以 dp[0][j] = dp[0][j - 1]。leetcode
第一列：对于 j = 0, i > 0，由于只能向下走，所以 dp[i][0] = dp[i - 1][0]。leetcode
在代码中，这些初始化逻辑是通过统一的循环和条件分支实现的，而不是单独写两层专门初始化第一行第一列：
dp[0][0]=1;for(i =0; i < m; i++){for(j =0; j < n; j++){if(i ==0&& j ==0)continue;if(i ==0) dp[i][j]= dp[i][j -1];elseif(j ==0) dp[i][j]= dp[i -1][j];else dp[i][j]= dp[i -1][j]+ dp[i][j -1];}}状态转移方程
对于一般位置 (i, j) 且 i > 0, j > 0：
dp[i][j]=dp[i−1][j]+dp[i][j−1]
对于第一行：
dp[j]=dp[j−1]
对于第一列：
dp[i]=dp[i−1]
用一句话概括：到达当前格子的路径数 = 来自上方的路径数 + 来自左方的路径数。leetcode
完整实现与返回值
使用 m * n 的二维数组 dp 存储所有状态，先用 malloc 分配空间并初始化为 0。leetcode
填表顺序：外层遍历行 i，内层遍历列 j，根据上面规则更新 dp[i][j]。leetcode
最终答案是右下角格子的状态值：dp[m - 1][n - 1]。leetcode
代码中将该值保存到 result，然后释放二维数组内存，最后 return result：
result = dp[m -1][n -1];for(i =0; i < m; i++)free(dp[i]);free(dp);return result;复杂度与优化思路
时间复杂度：每个格子只被计算一次，共 m×n 个格子，所以是 O(mn)。leetcode
空间复杂度：使用 m * n 的二维数组存储 dp 状态，空间复杂度为 O(mn)。leetcode
优化方向：由于每次转移只依赖当前行和上一行（或当前列和上一列），可以进一步使用一维数组实现空间优化到 O(n) 或 O(m)，这是常见的 follow-up。虽然当前版本使用的是二维 dp，但逻辑上已经为一维优化打下基础。leetcode
这篇博客从题意、状态设计到代码实现和复杂度分析，完整展示了如何用二维动态规划解决 Unique Paths 这类网格路径计数问题。通过这道题，可以系统地练习：如何定义状态、如何写出清晰的 base case、以及如何把转移关系翻译成代码。leetcode+1
