62. Unique Paths

Runtime error

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

これは遅すぎるようですが、一番簡単な方法で...

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

Runtime: 0 ms, faster than 100.00% of Java online submissions for Unique Paths.
Memory Usage: 35.9 MB, less than 48.61% of Java online submissions for Unique Paths.
数学がよければ、数学を利用することも可能だ.

from math import factorial
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return factorial(m + n - 2) // factorial(n - 1) // factorial(m - 1)