A robot is located at the top-left corner of amxngrid (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:mandnwill be at most 100.
題目如上，翻譯一下就是要找到所有的路徑寡喝，這種問題是一個比較簡單的問題驯击，當(dāng)然可以使用動態(tài)規(guī)劃，也就是記錄新矩陣的每個節(jié)點的數(shù)字等于到哪一個位置的路徑之和再往下走宿崭，所以最后一個點的數(shù)值就是到達該點的路徑和梆奈，也就是我們最終要求的數(shù)值晶疼。
假設(shè)原矩陣為m*n
那么新矩陣result：
result[0][0]=1;
result[0][j] = 1;
result[i][0] = 1;
result[i][j] = result[i][j-1]+result[i-1][j];
這樣就會發(fā)現(xiàn)：
假如是一個5*5的矩陣“
1 ? ? ? 1 ? ? ? 1 ? ? ? ?1 ? ? ? 1
1 ? ? ? 2 ? ? ? ?3 ? ? ? 4 ? ? ? ?5?
1 ? ? ? 3 ? ? ? ? 6 ? ? ? 10 ? ? ?15
1 ? ? ? 4 ? ? ? ? 10 ? ? ?20 ? ? ?35
1 ? ? ? 10 ? ? ? 20 ? ? ? 40 ? ? ?75
這樣發(fā)現(xiàn)特別像楊輝三角（本人數(shù)學(xué)太差-也不懂其中的奧秘）
總之垃你，我們還可以以另外一種方式計算，那就是數(shù)學(xué)方法：
相當(dāng)于從最左端到最右下角-我們需要向右走（n-1）步向下走（m-1）步
那么缭嫡，我們只需要在（m+n-2）步中選出向右走的或者向下走的步數(shù)就可以了：
因此很簡單的數(shù)學(xué)公式了缔御！
但是最簡單的數(shù)學(xué)公式如果暴力求解不是很樂觀，因此還是結(jié)合最開始的動態(tài)規(guī)劃妇蛀，這種動態(tài)規(guī)劃實際上就是一種組合數(shù)
所以分析到現(xiàn)在發(fā)現(xiàn)竟然是一樣的：
實現(xiàn)方法：
這是最簡單的一種了耕突，參考下面的鏈接可以得到計算組合數(shù)更好的方法了。
http://my.oschina.net/baoer1024/blog/62826
