62. 不同路径
查看题目中等
图
低频
解法一：动态规划
时间复杂度：O(m*n) | 空间复杂度：O(m*n) | 推荐使用
动画演示
准备就绪 - 输入网格的行数和列数，然后点击开始
代码实现
class Solution {
public int uniquePaths(int m, int n) {
// 创建一个m行n列的二维数组
int[][] dp = new int[m][n];
// 初始化第一行，所有元素都为1
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
// 初始化第一列，所有元素都为1
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
// 从(1,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(m*n)
使用动态规划解决不同路径问题。定义dp[i][j]为从起点(0,0)到(i,j)的不同路径数，状态转移方程为dp[i][j] = dp[i-1][j] + dp[i][j-1]，边界条件是第一行和第一列的所有元素都为1。