目錄

• topic
• 問題分析
  *不可行思路
  *可行思路
• 解決方案
• 代碼與測試結(jié)果
• 優(yōu)化&反思&擴(kuò)展
• 最后

Topic

---- from leetcode題庫，NO.576 Out of Boundary Paths

給定一個 m × n 的網(wǎng)格和一個球。球的起始坐標(biāo)為 (i,j) ，你可以將球移到相鄰的單元格內(nèi)，或者往上、下、左、右四個方向上移動使球穿過網(wǎng)格邊界。但是，你最多可以移動 **N **次。找出可以將球移出邊界的路徑數(shù)量。答案可能非常大，返回 結(jié)果 mod 10⁹ + 7 的值。

示例 1：

輸入: m = 2, n = 2, N = 2, i = 0, j = 0
輸出: 6
解釋:

image

示例 2：

輸入: m = 1, n = 3, N = 3, i = 0, j = 1
輸出: 12
解釋:

image

說明:

1. 球一旦出界，就不能再被移動回網(wǎng)格內(nèi)。
2. 網(wǎng)格的長度和高度在 [1,50] 的范圍內(nèi)。
3. N 在 [0,50] 的范圍內(nèi)。

問題分析

乍一看，此問題顯得略復(fù)雜，（反正我等小菜鳥是覺得好復(fù)雜，絕對不是leetcode標(biāo)注的‘中等’難度TAT...）
復(fù)雜問題簡單化，首先拆分問題：靠習(xí)慣性思維，我想想要用邏輯思維分析此問題，（用人話說就是想找個數(shù)學(xué)公式直接給算出來點(diǎn)啥）奈何，本人蠢，好像并沒有搞出什么可行的計(jì)算方法。

首先，看到這個問題，第一感覺是迭代。當(dāng)格子數(shù)大于1時(shí)，小球在格子里跑來跑去，完全可以亂跑，如果沒有N的限制，小球完全可以永遠(yuǎn)在格子里轉(zhuǎn)悠不出來（移動的步數(shù)無限大），步數(shù)無限大也就意味著路徑無限多，(這特么是想要跑死我的小本本嗎(⊙_⊙)...朕不干！)

恩，作為一個合格的心路歷程小本本，錯誤的想法也應(yīng)該如實(shí)記錄下來。下面是亂入的錯誤思路—>

不可行思路

先甭管前面的跑法啦，把球扔到格子里的任意位置，我可以根據(jù)（i,j）和（m,n）的數(shù)學(xué)關(guān)系算出球在該位置一步就走出去的路徑數(shù)。設(shè)路徑數(shù)為x，根據(jù)路徑數(shù)的不同可以把格子的空間分為三類：

1. 格子的四角，一步出格子的x=2；
2. 格子的四邊上除去四角的格子，一步出格子的x=1；
3. 格子的內(nèi)部，一步壓根兒就出不去，x=0
   抽象成數(shù)學(xué)問題就是：

• i==0或者i==m-1，表示球在第一行或者最后一行
• 同理，j==0或者j==n-1，表示球在第一列或者最后一列
• 以上四個條件都不滿足，說明球在大格子內(nèi)部，一步出不去，需要迭代解決
  上面三條，前兩條都很好表示，寶寶都已經(jīng)把前兩步的代碼寫好了，第三條搞不定（=.=）關(guān)于第三條不成熟想法是：不論球在格子內(nèi)部如何游走，想要出大格子，最后一步一定是從大格子四邊上的某格子，一步跨出去的，跨出去的方向有四種，i=0可以向上跨，j=0可以向左跨，i=m-1可以向下跨，j=n-1可以向右跨。而小球任意位置的移動都可以抽象成這四種跨越方式，貌似可以用遞歸模型呀~迭代->遞歸，前兩條所列的出大格子的方式可以作為遞歸的基例，那么最頭疼的問題就是遞歸鏈條了！一眼看不出來該怎么迭代起來，（頭疼TAT）那從數(shù)學(xué)歸納法的角度想想，要找到第x-1步到第x步之間的關(guān)系，也就是倒數(shù)第二步到最后一步的關(guān)系......
  要不我把大格子拆分試試？比如說最后一步球在第一行某位置，那在倒數(shù)第二行時(shí)，我就當(dāng)作第一行不存在，就相當(dāng)于球從第二行向上跨越上邊線出界啦，這樣只需要將起始行加一就行，同理可以對另外三邊做收縮處理~貌似可行，轉(zhuǎn)念一想，大事不好！倒數(shù)第二步的時(shí)候球不一定是從第二行跨越到第一行啊，小球完全可以在第一行內(nèi)部左右晃蕩很久之后，突然心情一好，就出去啦！什么鬼?。ㄋすP）
  噢，神吶，放過我吧，寶寶想不出來T_T，這小破球完全可以永遠(yuǎn)在格子里晃悠，愛出來不出來吧！

可行思路

以上，思路行不通T_T。。。
第二天，重新開始思考這個問題，重讀題干，突然發(fā)現(xiàn)我忽略了一個重要參數(shù)N，N用來限制球在格子內(nèi)移動的步數(shù)，只要步數(shù)有限，小球就不會永遠(yuǎn)在第一排晃悠啦_\(≧≦)/。

所以問題的關(guān)鍵（或者難點(diǎn)），必然跟參數(shù)N有關(guān)，球移動的步數(shù)必須小于指定參數(shù)N（此處手動為N打光加歡呼特效~）
因此本題迭代過程中，我們關(guān)注的兩個量，一個是計(jì)算結(jié)果--路徑數(shù)，另一個就是移動的步數(shù)，一條路徑上的移動步數(shù)由N來限定，就可以限定迭代的次數(shù)啦，即當(dāng)移動步數(shù)超過N時(shí)，即刻返回0。
好像可以在上面失敗的思路上引入步數(shù)限定參數(shù)來繼續(xù)思考噢，BUT！本寶寶倔強(qiáng)！昨天都摔過筆了，不想再繼續(xù)那個腦仁疼的思路了╭(╯^╰)╮哼！就要換個方向思考?。ㄕf白了就是自個兒慫，舊思路太復(fù)雜，八成是整不出來了，那就假裝敖嬌的放棄吧 ~~~如果有大神能按照上面我失敗的思路成功迭代出看來，請讓小弟膜拜一下，跪謝~~）

那么回歸正題，開始新的方向思考~
大方向依舊是迭代?；谜f~遞歸鏈條，昨天從后往前推失敗了，那今兒從前往后推試試。但是一定記得要考慮步數(shù)<=N!
設(shè)路徑數(shù)記錄為x，x初值為0，每走成功一條路就給x加一。
設(shè)步數(shù)為steps，那么最開始start_step=0，中間的某一步start_step不一定為0，小球每走一步steps加一，則對于下一步來說就是start_step比上一步加了1，（終于找到簡單的迭代單位啦~(≧≦)/~啦啦啦可喜可賀）且每走一步start_step要與N比較，一旦start_step要超過N，打?。〈寺房梢陨釛壛?，給x返回0吧。
接下來考慮每一步的行走情況：無論小球在網(wǎng)格的什么位置，一旦它還能走下一步，它都有四種方式走，即上下左右四個方向，每個方向走一步后，我可以通過坐標(biāo)和網(wǎng)格行列數(shù)的比較，判斷出它這一步是否出界了，一旦出界，路徑數(shù)計(jì)數(shù)x+=1，如果沒出界，那就繼續(xù)走下一步，形成遞歸。
思路看起來可行，著手形成解決方案~

解決方案

首先，定義變量：

• 輸出的路徑數(shù)x，初值為0，每行走一步計(jì)這一步之后所有的路徑數(shù)的初值都是0，因此每一步的函數(shù)中都重新定義局部變量x=0；
• 每一步開始時(shí)走過的步數(shù)start_step，用于統(tǒng)計(jì)走過的總步數(shù)與N比較，來退出迭代，與歷史值有關(guān)，因此需要通過參數(shù)傳遞來記錄；
• m表示網(wǎng)格行數(shù)，n表示網(wǎng)格列數(shù)，由函數(shù)參數(shù)給出，且在遞歸過程不會改變；
• i表示小球橫坐標(biāo)，j表示小球縱坐標(biāo)，隨著小球的移動坐標(biāo)值相應(yīng)變化。

然后，分析一次移動的過程：

1. 開始某次移動時(shí)，從本次移動開始至N步內(nèi)成功出界的路徑數(shù)為x，初始化x為0；
2. start_step由參數(shù)傳入，本次移動后步數(shù)需要加一，因此start_step先加一；
3. 判斷本次移動后總步數(shù)是否超過N，若超過N則從本次移動往后的所有路徑全無效，直接返回可行路徑數(shù)0（基例）；
4. 若本次移動后總步數(shù)不超過N則可以進(jìn)行本次移動：本次移動有四種可能，方向分別為上下左右；
5. 針對各方向移動的可能性做判斷：如果一步移動后出界，則路徑數(shù)x加一（基例）；若移動后未出界，則可以更新坐標(biāo)，繼續(xù)下一次的移動，從而形成遞歸；
6. 四個方向都判斷完后，返回本次移動的所有成功出界的路徑數(shù)x。

函數(shù)1：基例
對每次移動是否出界的判斷可以寫成函數(shù)形式：函數(shù)名為go1step（寶寶純屬在瞎起名字，回頭改0.0）；參數(shù)包括網(wǎng)格大小m,n、移動前坐標(biāo)i,j和移動方向direction，用direction分別為1、2、3、4表示上下左右四種移動方向；返回值為0或1，若移動后出界返回1，若未出界返回0。
本函數(shù)先根據(jù)參數(shù)direction區(qū)分本次將要移動的方向，再根據(jù)方向和坐標(biāo)判斷是否會出界。以direction=1為例，小球從（i,j）第i行第j列向上移動，當(dāng)且僅當(dāng)小球當(dāng)前位于網(wǎng)格第一排時(shí)才可能向上一步出界，因此判斷i是否為0即可知道向上是否出界，若i==0返回1，否則返回0。其他三方向同理。
注意：網(wǎng)格內(nèi)行列數(shù)從0開始計(jì)數(shù)，因此m行n列的網(wǎng)格的最下面一行是第(m-1)行，最右邊一列是第(n-1)列。

函數(shù)2：遞歸
此函數(shù)用來表示一次移動的過程，作為遞歸函數(shù)：函數(shù)名為go2step（不走心的函數(shù)名again，很明顯是根據(jù)第一個函數(shù)扒拉來的，好嘛，全通了之后再整理代碼時(shí)再改~）；參數(shù)包括網(wǎng)格大小m,n、移動前坐標(biāo)i,j、總步數(shù)上限N和本次移動開始時(shí)已走過的步數(shù)start_step;返回值為本函數(shù)中的局部變量x，表示可行的總路徑數(shù)。
本函數(shù)先判斷這一步是否可以走：如果走過這一步之后總步數(shù)超過N，甭管這一步是否出得去，后面的所有走法都是不可行的，所以直接返回可行的路徑數(shù)為0，此處是由總步數(shù)限制來結(jié)束遞歸的一個基例；如果走過這一步后總步數(shù)沒超過N，那么恭喜你，噢不，恭喜球，可以繼續(xù)往下走~
然后就是判斷本次移動怎么走的問題啦：我們的目標(biāo)是統(tǒng)計(jì)出所有可行的路徑數(shù)，因此每走一步都要考慮四個方向的所有走法，所求的是各方向的可行路徑和，因此每個方向得出的x都要累加。
對各方向的移動，先判斷本次移動后是否會出界：若出界，則一種走法結(jié)束，路徑數(shù)加一，此處為由主動出界來結(jié)束遞歸的一個基例；若不出界，則可以從本次移動后的坐標(biāo)開始走下一步，下一步的走法跟本次移動一樣，從而構(gòu)成遞歸函數(shù)，只需要根據(jù)方向更新一下下一步的起始坐標(biāo)即可，向上走時(shí)i減一，向下走時(shí)i加一，向左走時(shí)j減一，向右走時(shí)j加一。

以上，完成。

代碼與測試結(jié)果

將上面的方案寫成代碼，再加上運(yùn)行時(shí)間時(shí)間和測試用例打印，得到了本寶寶跑通的第一版代碼：

#coding utf-8
import time
def go1step(m, n, i, j,direction):
    if direction==1:
        return 1 if i==0 else 0
    elif direction==2:
        return 1 if i==m-1 else 0
    elif direction==3:
        return 1 if j == 0 else 0
    elif direction==4:
        return 1 if j == n-1 else 0
def go2step(m, n, i, j, N,start_step):
    x=0
    start_step+=1
    if start_step > N:
        return 0
    #----up
    x+=1 if go1step(m, n, i, j,1)==1 else go2step(m,n,i-1,j,N,start_step)
    #----down
    x += 1 if go1step(m, n, i, j,2)==1 else go2step(m,n,i+1,j,N,start_step)
    #----left
    x+=1 if go1step(m, n, i, j, 3)==1 else go2step(m,n,i,j-1,N,start_step)
    #----right
    x+=1 if go1step(m, n, i, j, 4)==1 else go2step(m,n,i,j+1,N,start_step)
    return x
t=time.time()
print(go2step(1, 3, 1, 1, 2, 0))
print(time.time()-t)

運(yùn)行代碼，換幾個測試函數(shù)試試，bingo，答案都正確~
愉快的把代碼粘到leetcode提交代碼，然而，leetcode提示我超出時(shí)間限制！

leetcode提示我超出時(shí)間限制！

TAT...我還能怎樣，嘗試優(yōu)化試試~

嘗試優(yōu)化
仔細(xì)一瞧，第一個函數(shù)完全可以不要，直接在第二個函數(shù)里替換成各方向的判斷條件就好啦~
而且上面的函數(shù)名怪奇怪的，貌似第二個函數(shù)更適合較go1step噢（走一步，夠直白哈哈哈哈哈嗝~）
另外代碼結(jié)構(gòu)不符合本寶寶嚴(yán)謹(jǐn)?shù)淖黠L(fēng)，怎么可以沒有main函數(shù)！
于是有了下面這版代碼：

#coding utf-8
import time
def go1step(m, n, i, j, N,start_step):
    x=0
    start_step+=1
    if start_step > N:
        return 0
    #----up
    x+=1 if i==0 else go1step(m,n,i-1,j,N,start_step)
    #----down
    x += 1 if i==(m-1) else go1step(m,n,i+1,j,N,start_step)
    #----left
    x+=1 if j==0 else go1step(m,n,i,j-1,N,start_step)
    #----right
    x+=1 if j==(n-1) else go1step(m,n,i,j+1,N,start_step)
    return x
def main():
    t=time.time()
    print(go1step(10,10,5,5,10,0))
    print(time.time()-t,'s')
if __name__ == '__main__':
    main()

再次運(yùn)行l(wèi)eetcode給出的超時(shí)的測試用例，amazing！時(shí)間減少看不少呢~
滿心歡喜再次去leetcode提交代碼，然而現(xiàn)實(shí)依舊殘酷，依舊超出時(shí)間限制=_=

依舊提示超出時(shí)間限制

優(yōu)化&反思&擴(kuò)展

優(yōu)化
其實(shí)上面嘗試優(yōu)化的代碼本質(zhì)上并沒有節(jié)省多少運(yùn)行時(shí)間，改動函數(shù)格式并沒有改變計(jì)算方法的時(shí)間復(fù)雜度和空間復(fù)雜度。
看提交記錄中顯示的共94個測試用例才通過了47個就超時(shí)了，估計(jì)后面的測試用例的網(wǎng)格更大，統(tǒng)計(jì)的最大移動步數(shù)更大，這樣看來我這種一一迭代的算法可能就是無法滿足本題的運(yùn)算需求和時(shí)間限制的。
看來想要滿足本題的要求，寶寶必須得尋求更優(yōu)的算法才行，比如說以下思路：

• 在步數(shù)限制的倒數(shù)第二步時(shí)，即N-1步時(shí)，判斷出本次移動將是最后一步，不再向各個方向都走，而是直接返回一步出界的方向數(shù)，此返回值可由坐標(biāo)和網(wǎng)格邊界直接判斷出，x∈[0,4];
• 根據(jù)leetcode給出的hints:

Hint 1
WIll traversing every path is fesaible? There are many possible paths for a small matrix. Try to optimize it.
Hint 2
Can we use some space to store the number of paths and updating them after every move?
Hint 3
One obvious thing: ball will go out of boundary only by crossing it. Also, there is only one possible way ball can go out of boundary from boundary cell except corner cells. From corner cell ball can go out in two different ways. Can you use this thing to solve the problem?

• 第一條沒懂啥意思：是否每條路徑都可行？一個小矩陣有很多種可能的路徑。試圖優(yōu)化它。？.？啥意思？是讓我把大網(wǎng)格切成小矩陣嗎？就算求出小矩陣的路徑數(shù)也不知道該怎么組合起來呀；
• 第二條好像蠻有道理的，但寶寶不知道該怎么具體實(shí)施：我們能否用一些空間來存儲路徑數(shù)，然后在每次移動后更新它？大概意思就是用空間來換時(shí)間吧，寶寶是用x來計(jì)路徑數(shù)的，而且每次移動都會重新初始化一個x，在完成本次移動后的所有路徑后，局部變量x被釋放，結(jié)果累加到上一步的x上。貌似有點(diǎn)浪費(fèi)空間，但不考慮空間復(fù)雜度的話，我也不知道還能怎樣來犧牲空間 換取時(shí)間=-=，求大神指點(diǎn)。
• 第三條貌似跟我前面那個沒想通的思路有點(diǎn)像：一個很明顯的事是：球只能通過越過邊界來出界。同時(shí)，除去角落的格子，球只有一種可能的方式來從邊界格子走出界。球從角落格子能有兩種出界方式。能用這個來解決問題嗎？這里所說的‘corner cell’就是我上面所說的‘四角格子’，‘boundary cell except corner cells’就是‘四邊上除去四角的格子’，而且我也能區(qū)分出這三類格子，但是就是沒想通怎么處理內(nèi)部格子的問題。。。求大神指點(diǎn)。

反正寶寶是沒想出別的啥可行的方案了=·=
反正不考慮時(shí)間問題的話寶寶的代碼在自己的環(huán)境中也都能算出正確答案=·=
反正leetcode上這個題一共只有20個人提交成功了，加上我都只有105個人提交了代碼呢=·=

一共只有20個人提交成功！

由前面的不可行的思路可以看出，寶寶的思考方式還是邏輯思維優(yōu)先，即使我知道所有的運(yùn)算都是由計(jì)算機(jī)來完成的，依舊想要尋求數(shù)學(xué)公式來解決問題，可能還是因?yàn)椴⒉簧瞄L計(jì)算思維。

計(jì)算思維是人類的第三種思維特征：

• 實(shí)證思維：實(shí)驗(yàn)&驗(yàn)證，以物理為代表
• 邏輯思維：推理&演繹，以數(shù)學(xué)為代表
• 計(jì)算思維：設(shè)計(jì)&構(gòu)造，以計(jì)算機(jī)為代表

計(jì)算思維是基于計(jì)算機(jī)的思維方式，抽象問題的計(jì)算過程，利用計(jì)算機(jī)自動化求解。
分析本題時(shí)，第一感覺就是要利用遞歸函數(shù)，大方向并沒有錯，卻在抽象問題過程中比較吃力。第一次的思路是想要通過推理和演繹找出計(jì)算路徑數(shù)的公式，然而即使知道要使用數(shù)學(xué)歸納法，也因?yàn)楹雎粤丝偛綌?shù)參數(shù)N而導(dǎo)致推理失敗。第二次的思路就是按照計(jì)算思維在分析問題了，卻仍是抽象問題的過程比較費(fèi)勁，而且最終抽象出的解法很簡單，或者說就是無腦，只是簡單的跑過所有的移動的可能性，從而統(tǒng)計(jì)總步數(shù)，導(dǎo)致在參數(shù)比較大時(shí)程序運(yùn)行慢。
回顧這兩種思維方式的產(chǎn)物，是不是兩者相結(jié)合效果能更好呢？比如說優(yōu)化方案中提到的，局部出界問題由推理和演繹直接算出總路徑數(shù)，全局移動過程再采用設(shè)計(jì)和構(gòu)造迭代的方法來實(shí)現(xiàn)；或者將m*n的網(wǎng)格分解為許多小矩陣，再由小矩陣之間的關(guān)系組合出全局的可行路線數(shù)。
即 實(shí)現(xiàn)邏輯思維與計(jì)算思維相結(jié)合才能更好的優(yōu)化此問題的解決方案。

擴(kuò)展
先甭管運(yùn)行速度如何，反正現(xiàn)在是能夠算出“N步之內(nèi)出界的所有路徑數(shù)”了，那么由此擴(kuò)展，將題干改成“走N步出界的路徑數(shù)”，也就很容易啦~
簡單推理就知道：
N步之內(nèi)出界路徑數(shù)=N-1步之內(nèi)出界路徑數(shù)+N步出界路徑數(shù)
因此，N步出界路徑數(shù)可有下面代碼實(shí)現(xiàn)：

def  GoOutAtStepN(m, n, i, j, N):
    return go1step(m, n, i, j, N,0)-go1step(m, n, i, j, N-1,0)

當(dāng)然，此解法的弊端依舊是時(shí)間復(fù)雜度太高，可能還有更優(yōu)解法。不再深入，如果有大神實(shí)現(xiàn)了，望賜教。

最后
碎嘴詩的第一篇博客，啰哩叭嗦的，終于寫完了，撒花~(≧≦)/~
寶寶知道，碎碎念對閱讀者來說并不友好，堅(jiān)持看到最后的都是真愛~_么么噠~
趁著寶寶還有力氣碼字，就想要多記錄下來一些，所以文中不僅有解題思路，也有不少寶寶的小情緒，誰讓寶寶愛寫日記呢，就當(dāng)是技術(shù)文檔與日記的結(jié)合吧~不過真的很累人誒，比手寫日記累多啦
為了學(xué)習(xí)為了進(jìn)步為了節(jié)約時(shí)間，以后還是少寫這種長篇大論的碎碎念好了...恩，以后還是以整理學(xué)習(xí)筆記為主好啦，要精簡！也方便自己回頭查看～至于日記嘛，專門開一類文集寫日記好啦~日記得設(shè)私密>^<
最后的最后，如果有幸能有大神看完這篇碎碎念，希望能針對本文的問題給出些意見建議，再次跪謝。