Ming
0%

LeetCode-62

Posted on Edited on In

题目

结果

代码

经典动态规划

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[][] path = new int[m][n];
        path[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) {
                    path[i][j] += path[i - 1][j];
                }
                if (j > 0) {
                    path[i][j] += path[i][j - 1];
                }
            }
        }
        return path[m - 1][n - 1];
    }
}

稍加优化

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

复杂度

时间复杂度：O（M*N）

空间复杂度：O（N），优化后