Leetcode之Unique Paths 问题

问题描述：

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?

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

Note: m and n will be at most 100.

问题来源：Unique Paths (详细地址：https://leetcode.com/problems/unique-paths/description/)

思路分析：

解法一：这道题和前面的一道题(Minimum Path Sum)非常的相似，差别只是数组中的元素不同，在这需要给每个格子赋值，我们指定首行和首列的大小都为1，然后其他的格子和minimum path sum的思路是差不多的，在这不是取最小值，而是把二者加起来，即：dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。同样的，我们也可以采用一维数组进行简化，简化出来的效果就是dp[j]=dp[j-1]+dp[j]。另外，还有一个区别就是在这每一个dp[0]一定是1，所以遍历每一行的时候无需更改，只需要从1开始就行了。

解法二：可以直接使用公式来解决，组合数学学过的话，肯定马上就能想到了，要走到最右下角，必须经历m-1步往下走，n-1步往右走，所以得到的结果就是(m-1+n-1)/(m-1)!(n-1)!=(m+n-2)!/(m-1)!(n-1)!

代码：

二维数组：

一维数组：

下面的解法也是对的：