1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < dp[0].length; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
}

常规的2D dp解法.
时间复杂度: O(m * n)
空间复杂度: O(m * n)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j > 0)
                    dp[j] += dp[j - 1];
            }
        }
        return dp[dp.length - 1];
    }
}

这个解法非常巧妙, 使用1D array. 1D array记录的是到我们即将要遍历的某行上面一行所有格子的path. 比如我们要遍历第3行. 那么dp记录的就是到第2行每个格子的path的数目.

先从第0行开始, 由于第0行上面没东西, 那么让dp所有element为0即可, 由于int array初始化就是0, 于是我们不需要进行初始化. 由于给定条件是从左上角出发, 因此dp[0]需要初始化为1, 也就是到左上角这个格子有且只有一种走法. 然后我们往右走, 到第一个格子, 此时dp[1]存的是到上面一行第一个格子path的数目, 此时上面没有行, dp[1]是0; dp[0]存的是到第0行第0个格子的path的数目, 此时是1. 这两个刚好是我们想要的到该格子上方格子以及左侧格子的path的数目, 因此把dp[1]更新为dp[0] + dp[1]即可. 按照这个思路, 更新第0行. 更新完后, dp存的是到第0行每个格子的path的数目. 也就是dp[i]表示的是到第0行第i个格子的path的数目.

接下来我们来到第1行. 从第0个元素开始, 由于它没有左边格子, 因此只需要看上边格子即可. 上边格子也就是第0行第0个格子, 到它的path数目就是此时的dp[0], 因此dp[0]的新值就是dp0 + 0(到左边格子的path数目),也就是还是dp[0],此时虽然dp[0]的值没有变,但是它表示的意义确实到达第1行第0个格子的path数目. 然后我们来到第1行第一个格子, 此时我们需要第1行左边格子和上边格子的path数. 到左边格子的path就是dp[0], 由于dp[1]还没有更新, 因此dp[1]此时是到第0行第一个格子的path数目也就是第一行第一个格子上面的格子, 正是我们想要的. 因此我们把dp[1]更新为dp[0] + dp[1], 使得dp[1]更新为到第1行第一个格子的path数目. 按照这个逻辑往下更新即可.

这个思路利用的就是不必要存到所有行所有格子的path数目, 只需要存上一行的即可.

时间复杂度: O(m * n)
空间复杂度: O(n)