LeetCode 62. 不同路径

题目描述

给定一个 m × n 的网格，机器人从左上角出发，每次只能向下或者向右移动一步，到达右下角。求有多少种不同的路径。

解题思路

使用动态规划（Dynamic Programming）解决。

1. 定义状态：dp[i][j] 表示从起点到达位置 (i, j) 的路径数。
2. 状态转移方程：由于只能向下或向右移动，到达 (i, j) 只能从上方 (i-1, j) 或左方 (i, j-1) 过来。因此 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
3. 边界条件：第一行和第一列的所有位置只有一种走法（一直向右或一直向下），即初始化为 1。

代码实现

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化第一列
        for (int i = 1; i <= m; i++) {
            dp[i][1] = 1;
        }
        // 初始化第一行
        for (int i = 1; i <= n; i++) {
            dp[1][i] = 1;
        }
        
        // 填充 DP 表
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
         dp[m][n];
    }
}