LeetCode 62 - Unique Paths

LeetCode 73 - Unique Paths II
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
https://leetcode.com/discuss/17530/java-dp-solution-with-complexity-o-n-m

public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        if (m == 1 || n == 1) {
            return 1;
        }

        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
}

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];

    }

    int uniquePaths(int m, int n) {
 4         vector<int>dp(n+1, 1);
 5         for(int i = 2; i <= m; i++)
 6             for(int j = 2; j <= n; j++)
 7                 dp[j] =  dp[j] + dp[j-1];
 8         return dp[n]; 

9 }
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
X. Math
https://leetcode.com/discuss/9110/my-ac-solution-using-formula

First of all you should understand that we need to do n + m - 2 movements : m - 1 down, n - 1 right, because we start from cell (1, 1).

Secondly, the path it is the sequence of movements( go down / go right), therefore we can say that two paths are different when there is i-th (1 .. m + n - 2) movement in path1 differ i-th movement in path2.

So, how we can build paths. Let's choose (n - 1) movements(number of steps to the right) from (m + n - 2), and rest (m - 1) is (number of steps down).

I think now it is obvious that count of different paths are all combinations (n - 1) movements from (m + n-2).

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; }
https://discuss.leetcode.com/topic/19613/math-solution-o-1-space
https://discuss.leetcode.com/topic/31724/java-solution-0ms-4lines

This is a combinatorial problem and can be solved without DP. For mxn grid, robot has to move exactly m-1 steps down and n-1 steps right and these can be done in any order.

For the eg., given in question, 3x7 matrix, robot needs to take 2+6 = 8 steps with 2 down and 6 right in any order. That is nothing but a permutation problem. Denote down as 'D' and right as 'R', following is one of the path :-

D R R R D R R R

We have to tell the total number of permutations of the above given word. So, decrease both m & n by 1 and apply following formula:-

Total permutations = (m+n)! / (m! * n!)

    public int uniquePaths(int m, int n) {
        if(m == 1 || n == 1)
            return 1;
        m--;
        n--;
        if(m < n) {              // Swap, so that m is the bigger number
            m = m + n;
            n = m - n;
            m = m - n;
        }
        long res = 1;
        int j = 1;
        for(int i = m+1; i <= m+n; i++, j++){       // Instead of taking factorial, keep on multiply & divide
            res *= i;
            res /= j;
        }
            
        return (int)res;
    }

http://bookshadow.com/weblog/2015/10/11/leetcode-unique-paths/

题目可以转化为下面的问题：

求m - 1个白球，n - 1个黑球的排列方式

公式为：C(m + n - 2, n - 1)

(m+n-2)!/(m-1)!(n-1)!
http://agoodcode.blogspot.com/2014/04/leetcode-unique-paths.html
O(min(m,n))
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;
    }

class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ if m < n: m, n = n, m mul = lambda x, y: reduce(operator.mul, range(x, y), 1) return mul(m, m + n - 1) / mul(1, n)

X. DFS
http://www.programcreek.com/2014/05/leetcode-unique-paths-java/

public int uniquePaths(int m, int n) { return dfs(0,0,m,n); }   public int dfs(int i, int j, int m, int n){ if(i==m-1 && j==n-1){ return 1; }   if(i<m-1 && j<n-1){ return dfs(i+1,j,m,n) + dfs(i,j+1,m,n); }   if(i<m-1){ return dfs(i+1,j,m,n); }   if(j<n-1){ return dfs(i,j+1,m,n); }   return 0; }

Read full article from Unique Paths | LeetCode