62. Unique Paths

题目分析

这是一道典型的动态规划题。

代码

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

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

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

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

将问题转换成排列组合问题，时间复杂度 O(n)，空间复杂度 O(1)

class Solution {
    public int uniquePaths(int m, int n) {
        double res = 1;
        double count = m + n - 2;
        for(int i = 1; i < m; i++) {
            res *= (count + 1 - i) / i; 
        }
        return (int) Math.round(res);
    }
}