想更方便閱讀代碼的朋友可以點(diǎn)這里。
題目描述：
一個(gè)機(jī)器人位于一個(gè)?m x n?網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）流译。
機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）里覆。
問總共有多少條不同的路徑畜埋？
例如，上圖是一個(gè)7 x 3 的網(wǎng)格烟瞧。有多少可能的路徑诗鸭？
說明：m?和?n?的值均不超過 100。
示例?1:
輸入: m = 3, n = 2
輸出: 3
解釋:
從左上角開始参滴，總共有 3 條路徑可以到達(dá)右下角强岸。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例?2:
輸入: m = 7, n = 3
輸出: 28
問題分析：
? ? ? ?這是一個(gè)尋找路徑條數(shù)的問題，而且存在一個(gè)限制條件：機(jī)器人只能向右走或者向下走砾赔，這樣的話就意味著如鏡中不存在向左走再向右走這樣無解的情況蝌箍。除此我們對(duì)圖進(jìn)行分析可以知道，當(dāng)機(jī)器人走到了與終點(diǎn)同一行或者同一列的位置時(shí)暴心，就只有一條路徑方案了妓盲，敏銳的人可能發(fā)現(xiàn)了，這個(gè)可以做為遞歸的終止條件专普，那么我們?nèi)绾未_定遞歸的劃分呢悯衬？遞歸的劃分其實(shí)在題目中已經(jīng)告訴了我們方法。題目高告訴我們機(jī)器人只能向下或者向右檀夹，這是不是就意味著兩條遞歸路徑呢筋粗。
? ? ? 舉個(gè)實(shí)例，就假設(shè)當(dāng)前機(jī)器人在坐標(biāo)(1,5)處击胜，終點(diǎn)在(2,6)處亏狰，這樣的話役纹，我們可以發(fā)現(xiàn)機(jī)器人向右走得時(shí)候只有一條路徑偶摔，向下走得時(shí)候也只有一條路徑，那么從點(diǎn)(1,5)到(2,6）就有turnRinght+turnDown=2種路徑了促脉，在向上一層辰斋，例如(1,4)到（2策州，6）向下只有一條路徑，向右走一步就到了(1,5)由之前的結(jié)果我們就可以知道有兩條路徑宫仗，這樣的話够挂，(1,4)到（2，6）有3條路徑藕夫。
代碼如下：
class Solution {
? ? private int[][] cache;? //緩存 備忘錄模式
? ? public int uniquePaths(int column, int row) {
? ? ? ? if(column==0||row==0){
? ? ? ? ? ? return 0;
? ? ? ? }
? ? ? ? cache=new int[row][column];
? ? ? ? return recursion(column,row,0,0);
? ? }
? ? public int recursion(int column,int row,int x,int y){
? ? ? ? if(column-1==y||row-1==x){
? ? ? ? ? ? return 1;
? ? ? ? }
? ? ? ? if(cache[x][y]!=0){
? ? ? ? ? ? return cache[x][y];
? ? ? ? }
? ? ? ? int right= recursion(column,row,x+1,y);
? ? ? ? int down= recursion(column,row,x,y+1);
? ? ? ? cache[x][y]=right+down;
? ? ? ? return right+down;
? ? }
}
因?yàn)閱渭兊氖褂眠f歸會(huì)使得的時(shí)間和空間消耗過大孽糖，不滿足題意，所以在代碼中使用了備忘錄模式毅贮，添加了一個(gè)緩存用來存儲(chǔ)已經(jīng)走過的點(diǎn)到終點(diǎn)的路徑數(shù)量办悟。
