目錄

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

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é)公式直接給算出來點啥）奈何，本人蠢挺峡，好像并沒有搞出什么可行的計算方法葵孤。

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

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

不可行思路

先甭管前面的跑法啦叨吮，把球扔到格子里的任意位置辆布，我可以根據(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ù)第二行時玄妈，我就當(dāng)作第一行不存在乾吻，就相當(dāng)于球從第二行向上跨越上邊線出界啦，這樣只需要將起始行加一就行措近，同理可以對另外三邊做收縮處理~貌似可行，轉(zhuǎn)念一想女淑，大事不好瞭郑！倒數(shù)第二步的時候球不一定是從第二行跨越到第一行啊，小球完全可以在第一行內(nèi)部左右晃蕩很久之后鸭你，突然心情一好屈张，就出去啦擒权！什么鬼！（摔筆）
  噢阁谆，神吶碳抄，放過我吧，寶寶想不出來T_T场绿，這小破球完全可以永遠(yuǎn)在格子里晃悠剖效，愛出來不出來吧！

可行思路

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

所以問題的關(guān)鍵（或者難點），必然跟參數(shù)N有關(guān)瓣颅，球移動的步數(shù)必須小于指定參數(shù)N（此處手動為N打光加歡呼特效~）
因此本題迭代過程中倦逐，我們關(guān)注的兩個量，一個是計算結(jié)果--路徑數(shù)宫补，另一個就是移動的步數(shù)檬姥，一條路徑上的移動步數(shù)由N來限定，就可以限定迭代的次數(shù)啦粉怕，即當(dāng)移動步數(shù)超過N時健民，即刻返回0。
好像可以在上面失敗的思路上引入步數(shù)限定參數(shù)來繼續(xù)思考噢贫贝，BUT秉犹！本寶寶倔強！昨天都摔過筆了稚晚，不想再繼續(xù)那個腦仁疼的思路了╭(╯^╰)╮哼崇堵！就要換個方向思考！（說白了就是自個兒慫客燕，舊思路太復(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ù)計數(shù)x+=1趴俘，如果沒出界睹簇，那就繼續(xù)走下一步，形成遞歸寥闪。
思路看起來可行太惠，著手形成解決方案~

解決方案

首先，定義變量：

• 輸出的路徑數(shù)x疲憋，初值為0凿渊，每行走一步計這一步之后所有的路徑數(shù)的初值都是0，因此每一步的函數(shù)中都重新定義局部變量x=0；
• 每一步開始時走過的步數(shù)start_step嗽元，用于統(tǒng)計走過的總步數(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. 開始某次移動時，從本次移動開始至N步內(nèi)成功出界的路徑數(shù)為x刽肠，初始化x為0溃肪；
2. start_step由參數(shù)傳入，本次移動后步數(shù)需要加一音五，因此start_step先加一惫撰；
3. 判斷本次移動后總步數(shù)是否超過N，若超過N則從本次移動往后的所有路徑全無效躺涝，直接返回可行路徑數(shù)0（基例）厨钻；
4. 若本次移動后總步數(shù)不超過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)格第一排時才可能向上一步出界，因此判斷i是否為0即可知道向上是否出界围辙，若i==0返回1我碟，否則返回0。其他三方向同理姚建。
注意：網(wǎng)格內(nèi)行列數(shù)從0開始計數(shù)矫俺，因此m行n列的網(wǎng)格的最下面一行是第(m-1)行，最右邊一列是第(n-1)列掸冤。

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

以上造壮，完成。

代碼與測試結(jié)果

將上面的方案寫成代碼骂束，再加上運行時間時間和測試用例打印耳璧，得到了本寶寶跑通的第一版代碼：

#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)

運行代碼，換幾個測試函數(shù)試試展箱，bingo旨枯，答案都正確~
愉快的把代碼粘到leetcode提交代碼，然而混驰，leetcode提示我超出時間限制攀隔！

leetcode提示我超出時間限制！

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()

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

依舊提示超出時間限制

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

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

• 在步數(shù)限制的倒數(shù)第二步時幼驶，即N-1步時艾杏，判斷出本次移動將是最后一步，不再向各個方向都走盅藻，而是直接返回一步出界的方向數(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ù)眶俩，然后在每次移動后更新它莹汤？大概意思就是用空間來換時間吧，寶寶是用x來計路徑數(shù)的颠印，而且每次移動都會重新初始化一個x体啰，在完成本次移動后的所有路徑后，局部變量x被釋放嗽仪，結(jié)果累加到上一步的x上荒勇。貌似有點浪費空間，但不考慮空間復(fù)雜度的話闻坚，我也不知道還能怎樣來犧牲空間 換取時間=-=沽翔，求大神指點。
• 第三條貌似跟我前面那個沒想通的思路有點像：一個很明顯的事是：球只能通過越過邊界來出界窿凤。同時仅偎，除去角落的格子，球只有一種可能的方式來從邊界格子走出界雳殊。球從角落格子能有兩種出界方式橘沥。能用這個來解決問題嗎？這里所說的‘corner cell’就是我上面所說的‘四角格子’夯秃，‘boundary cell except corner cells’就是‘四邊上除去四角的格子’座咆，而且我也能區(qū)分出這三類格子痢艺，但是就是沒想通怎么處理內(nèi)部格子的問題。。。求大神指點椎椰。

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

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

由前面的不可行的思路可以看出，寶寶的思考方式還是邏輯思維優(yōu)先搬素，即使我知道所有的運算都是由計算機來完成的呵晨，依舊想要尋求數(shù)學(xué)公式來解決問題，可能還是因為并不擅長計算思維熬尺。

計算思維是人類的第三種思維特征：

• 實證思維：實驗&驗證摸屠，以物理為代表
• 邏輯思維：推理&演繹，以數(shù)學(xué)為代表
• 計算思維：設(shè)計&構(gòu)造粱哼，以計算機為代表

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

擴展
先甭管運行速度如何韧拒，反正現(xiàn)在是能夠算出“N步之內(nèi)出界的所有路徑數(shù)”了，那么由此擴展十性，將題干改成“走N步出界的路徑數(shù)”叛溢，也就很容易啦~
簡單推理就知道：
N步之內(nèi)出界路徑數(shù)=N-1步之內(nèi)出界路徑數(shù)+N步出界路徑數(shù)
因此，N步出界路徑數(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)然劲适，此解法的弊端依舊是時間復(fù)雜度太高楷掉，可能還有更優(yōu)解法。不再深入霞势，如果有大神實現(xiàn)了烹植，望賜教。

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