62. Unique Paths

题目：

A robot is located at the top-left corner of a m x ngrid (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?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

链接： http://leetcode.com/problems/unique-paths/

4/16/2017

1ms，8%

一开始几乎忘记怎么做了，决定好好研究DP

注意：

第7行初始值设为1

 1 public class Solution {
 2     public int uniquePaths(int m, int n) {
 3         int[][] dp = new int[m][n];
 4         
 5         for (int i = 0; i < m; i++) {
 6             for (int j = 0; j < n; j++) {
 7                 if (i == 0 && j == 0) dp[i][j] = 1;
 8                 else if (i == 0) dp[i][j] = dp[i][j - 1];
 9                 else if (j == 0) dp[i][j] = dp[i - 1][j];
10                 else dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
11             }
12         }
13         return dp[m - 1][n - 1];
14     }
15 }

还可以用一维数组rolling array来计算，参考别人答案。多一个元素是为了免掉第一次的全部赋值。

为什么用了一维数组还是可以的呢？虽然是一维，但是每次i有变化时,res又被重复使用，之前dp[i-1][j]这一部分是在之前算过了。（感觉还是没有解释好）

 1 public class Solution {
 2     public int uniquePaths(int m, int n) {
 3         if (m < 0 || n < 0) return 0;
 4         int[] dp = new int[n + 1];
 5         dp[0] = 1;
 6         
 7         for (int i = 1; i <= m; i++) {
 8             for (int j = 1; j <= n; j++) {
 9                 dp[j] += dp[j - 1];
10             }
11         }
12         return dp[n - 1];
13     }
14 }

关于rolling array很详细的解释

https://discuss.leetcode.com/topic/15265/0ms-5-lines-dp-solution-in-c-with-explanations

如何实现combination的实现

https://discuss.leetcode.com/topic/2734/my-ac-solution-using-formula

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

通过permutation来实现combination

https://discuss.leetcode.com/topic/19613/math-solution-o-1-space

 1 public class Solution {
 2     public int uniquePaths(int m, int n) {
 3         if(m == 1 || n == 1)
 4             return 1;
 5         m--;
 6         n--;
 7         if(m < n) {              // Swap, so that m is the bigger number
 8             m = m + n;
 9             n = m - n;
10             m = m - n;
11         }
12         long res = 1;
13         int j = 1;
14         for(int i = m+1; i <= m+n; i++, j++){       // Instead of taking factorial, keep on multiply & divide
15             res *= i;
16             res /= j;
17         }
18             
19         return (int)res;
20     }
21 }