题目描述

题目链接：62. 不同路径

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

1 2	输入：m = 3, n = 7 输出：28

示例1：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例2：

1 2	输入：m = 7, n = 3 输出：28

示例3：

1 2	输入：m = 3, n = 3 输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10(9)

我的题解

方法一：动态规划

思路

假设当前位置为(i, j)，那么有两种路径可以到达当前位置，即(i-1, j)和(i, j-1)，因此到达当前位置的路径数可由左边和上边的路径推出，因此递推公式为：

1	dp[i][j] = dp[i-1][j] + dp[i][j-1]

代码

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[1][1] = 1;
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}

使用滚动数组优化：

class Solution {
    public int uniquePaths(int m, int n) {
        int max = Math.max(m, n);
        int min = Math.min(m, n);
        int[] dp = new int[min];
        for (int i = 0; i < max; i++) {
            for (int j = 0; j < min; j++) {
                if (i == 0 || j == 0) {
                    dp[j] = 1;
                } else {
                    dp[j] += dp[j - 1];
                }
            }
        }
        return dp[min - 1];
    }
}