LeetCode 62. 不同路径 题目描述题目级别中等一个机器人位于一个m x n网格的左上角 起始点在下图中标记为 “Start” 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。问总共有多少条不同的路径示例 1:输入m 3,n 7输出28 破题思路二维动态规划基础模型机器人每次只能向右或向下走。这就意味着机器人想要到达网格中的某个格子(i, j)它只有可能是从两个方向走过来的从它上方的格子(i-1, j)走下来。从它左方的格子(i, j-1)走过来。状态定义定义dp[i][j]为走到格子(i, j)共有多少条不同的路径。状态转移方程既然只有两条路能汇聚到当前格子那么到达当前格子的路径总数就等于到达上方格子的路径数加上到达左方格子的路径数dp[i][j] dp[i - 1][j] dp[i][j - 1]初始化边界条件第一行的所有格子因为机器人只能向右/向下所以要想到达第一行的任何一个格子只能一直向右走别无选择。因此第一行的所有格子路径数都是1。第一列的所有格子同理只能一直向下走。因此第一列的所有格子路径数也都是1。 C 代码实现 (标准二维数组)classSolution{public:intuniquePaths(intm,intn){// 规范写法使用 vector 开辟 2D 数组初始化全为 0vectorvectorintdp(m,vectorint(n,0));// 遍历整个网格for(inti0;im;i){for(intj0;jn;j){// 第一行或第一列只有一条直线路径可达if(i0||j0){dp[i][j]1;}else{// 状态转移当前路径数 上方路径数 左方路径数dp[i][j]dp[i-1][j]dp[i][j-1];}}}// 返回右下角格子的路径总数returndp[m-1][n-1];}};