Leetcode 62: Unique Paths

https://leetcode.com/problems/unique-paths/

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        if m <0 or n < 0:
            return 0
        
        ways = [[0] * n for _ in xrange(m)]
        for i in xrange(0, n):
            ways[0][i] = 1
        for j in xrange(0,m):
            ways[j][0] = 1
        
        for j in xrange(1,m):
            for i in xrange(1,n):
                ways[j][i] = ways[j-1][i] + ways[j][i-1]
        
        return ways[-1][-1]
        

Idea

Use very naive idea of Dynamic Programming by creating an m*n matrix ,`ways`. Each cell records the number of ways that can reach there. At the end, just return `ways[-1][-1]`. This requires `O(m*n)` time and `O(m*n)` space.

The space can be reduced by observing that you are either updating `ways` row by row or column by column. This means you only need to keep O(m) or O(n) space in memory all the time. Below is the updated code (not in Python) (https://leetcode.com/discuss/38353/0ms-5-lines-dp-solution-in-c-with-explanations):

class Solution {
    int uniquePaths(int m, int n) {
        if (m > n) return uniquePaths(n, m);
        vector<int> cur(m, 1);
        for (int j = 1; j < n; j++)
            for (int i = 1; i < m; i++)
                cur[i] += cur[i - 1]; 
        return cur[m - 1];
    }
}; 

Another idea is to derive `ways[-1][-1]` using combination formula: you always need `n+m-2` steps to reach (m,n) from (1,1) by either going down or right. Among the `n+m-2` steps, you need exactly `m-1` steps going down. Therefore ways[-1][-1] = $latex C_{n+m-2}^{m-1}$. The code implementing this idea (https://leetcode.com/discuss/9110/my-ac-solution-using-formula):

class Solution {
    public:
        int uniquePaths(int m, int n) {
            int N = n + m - 2;// how much steps we need to do
            int k = m - 1; // number of steps that need to go down
            double res = 1;
            // here we calculate the total possible path number 
            // Combination(N, k) = n! / (k!(n - k)!)
            // reduce the numerator and denominator and get
            // C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
            for (int i = 1; i <= k; i++)
                res = res * (N - k + i) / i;
            return (int)res;
        }
    };