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?

img

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

Note: m and n will be at most 100.

思路

这是一道比较直白的找规律题。只有一行的情况无需多言，我们来看看示例中三行的情况，有多少个Unique Path。

由图可知，我们要想到达终点，需要至少往纵向的方向走两步，横向的方向走六步。我们只关心纵向的走法。因为一旦纵向的走法确定了，横向的走法也是唯一的了。

我们从起点向下走，走一格的纵向走法有六种。而这六种走法中，分别对应了不同的第二格的走法。它们的走法数目分别是6、5、4、3、2、1。据此我们可以得到第16行while语句中间循环的内容。行数的增加，只是增加循环的深度而已。将所有可能性求和，我们就可以得到最终的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int uniquePaths(int m, int n) {
        int line = min(m, n);
        int col = max(m, n);
        vector<int> result;
        
        if(line <= 0) return 0;
        else if(line == 1) return line;
        else{
            for (int i = 0; i < col; i++){
                result.push_back(1);
            }
            vector<int> tmp(col);
            int i = 2;
            while(i < line){
                for (int i = 0; i < col; i++){
                    tmp[i] = 0;
                    for(int j = 0; j <= i; j++){
                        tmp[i] += result[j];
                    }
                }
                i++;
                result = tmp;
            }
        }
        int ans = 0;
        for (int i = 0; i < col; i++){
            ans += result[i];
        }
        return ans;
    }
};