Unique Paths | LeetCode

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

dp[m][n] = dp[m][n-1] + dp[m-1][n] where dp[m][n] denotes the number of unique paths
Backtracking Solution:
Code from http://www.cnblogs.com/TenosDoIt/p/3704091.html
int uniquePaths(int m, int n) {
if(m == 1 || n == 1)return 1;
else return  uniquePaths(m, n - 1) + uniquePaths(m - 1, n);
}
Dynamic Programming Solution using Bottom-up Approach:
O(n^2) space & time: Code from http://joycelearning.blogspot.com/2013/10/leetcode-unique-paths.html

public int uniquePaths(int m, int n) {

        int[][] res = new int[m][n];

         

        // init left

        for(int i = 0; i < m; i++) {

            res[i][0] = 1;

        }

        // init top

        for(int j = 0; j < n; j++) {

            res[0][j] = 1;

        }

         

        // add values

        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(n^2) time, O(n) space

public int uniquePaths(int m, int n) {

        int[] res = new int[n];

         

        // init array

        for(int j = 0; j < n; j++) {

            res[j] = 1;

        }

         

        // add values

        for(int i = 1; i < m; i++) {

            // reset the head to 1 (simulate the next row head)

            // similar to set all left most elements in a 2D array to 1

            res[0] = 1;

            for(int j = 1; j < n; j++) {

                res[j] = res[j - 1] + res[j];

            }

        }

         

        return res[n - 1];

    }

No matter how you choose your path, they must have exactly (m+n-2) moves contain m−1 "down" and n−1 "right". A path is simply a combination you selectm−1 (or n−1 ) moves from them and assign it with "down" (or "right"). As a result, you just need to calculate the number of such combinations.
其实这个和组合数有关，对于m*n的网格，从左上角走到右下角，总共需要走m+n-2步，其中必定有m-1步是朝右走，n-1步是朝下走，那么这个问题的答案就是组合数：, 这里需要注意的是求组合数时防止乘法溢出 
Code from http://www.darrensunny.me/leetcode-unique-paths/

public int uniquePaths(int m, int n) {

        // Formulation: find the number of combinations when picking m-1 (or n-1) items

        // from m+n-2 different items, which is (m+n-2)! / ((m-1)!(n-1)!)

        // = m(m+1)...(m+n-2) / (n-1)! (for ease of computation, if m is larger)

        int smaller, larger;

        if (m < n) {

            smaller = m-1;

            larger = n-1;

        } else {

            smaller = n-1;

            larger = m-1;

        }

        long denom = 1, numer = 1;      // Use "long" in case of overflow

        for (int i = 1; i <= smaller; i++) {

            denom *= i;

            numer *= larger+i;

        }

        return (int)(numer/denom);

    }

Code from http://www.cnblogs.com/TenosDoIt/p/3704091.html
int uniquePaths(int m, int n) {
        return combination(m+n-2, m-1);
    }
   
    int combination(int a, int b)
    {
        if(b > (a >> 1))b = a - b;
        long long res = 1;
        for(int i = 1; i <= b; i++)
            res = res * (a - i + 1) / i;
        return res;
    }
Read full article from Unique Paths | LeetCode