題目
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?
分析
一個機(jī)器人在一個m X n的網(wǎng)格左上方始腾，只能向下或者向右移動空执，有多少可能的路徑能夠到達(dá)最底下的網(wǎng)格。假如使用路徑搜索等遞歸算法辨绊，可能會超時。
我們可以在Excel中計算總路徑數(shù)门坷，就會發(fā)現(xiàn)其中的規(guī)律。下面列出(m,n)的結(jié)果矩陣：
| n\m |1 | 2| 3|4|5|6|
| :-------- | --------:| :------: |:-------- | :-------- | :-------- |
| 1 |1 | 1 | 1| 1| 1| 1|
| 2 |1 | 2| 3|4|5|6|
| 3 | 1| 3| 6|10|15|21|
| 4 | 1| 4| 10|20|35|56|
| 5 | 1| 5| 15|35|70|126|
| 6 | 1| 6| 21|56|126 | 258|
可以看到這樣的規(guī)律（m,n）=(m-1,n)+(m,n-1),左邊的數(shù)字加上上邊的數(shù)字能夠得到該數(shù)字默蚌，也就是動態(tài)規(guī)劃的思想，要達(dá)到（m,n）的位置绸吸，只有兩個路徑（m,n-1）和(m-1,n)，而這兩個之前計算過了锦茁，就不用計算了攘轩。因此可以列一個100X100的表，通過循環(huán)把所有的數(shù)都算出來码俩，然后輸出結(jié)果即可度帮。
其他人的方法：反正是向下和向右，不用管其順序握玛，可以看做數(shù)學(xué)的組合問題够傍，隨意組合，之后由于一直朝一個方向算一條獨(dú)特的路徑挠铲，因此再除去某數(shù)的階層冕屯！。
int uniquePaths(int m, int n) {
int ans[101][101]={1};
for(int i=1;i<101;i++)
ans[1][i]=1;
ans[2][1]=1;
for(int i=2;i<101;i++)
{
ans[i][i]=2*ans[i-1][i];
for(int j=i+1;j<101;j++)
{
ans[i][j]=ans[i][j-1]+ans[i-1][j];
}
}
if(m>n)
return ans[n][m];
else
return ans[m][n];
}
