D(ynamic) P(rogramming)

https://zhuanlan.zhihu.com/p/365698607

可以參考

然后針對方格問題,如 P1002

先拿斬馬刀

給他馬一刀

簡單地,我們得到以下事實:

通往任意一點的路線數(shù)量等于相鄰兩點數(shù)量的和.

(只能由這兩點到這一點,既然走到這兩點的路線數(shù)是一定的,那走到這個點自然不會變,只是在原有路線后加了一個點而已,類似于1+1+....)

也就是

也就是圖中表示的兩個箭頭:上面和左邊加起來就等于這一格的數(shù)字

有點像楊輝三角

其他幾個條件也很簡單:

邊界:x或y中有一個為0,也就是坐標邊界,那必然為1(圖中給出),因為除了直線無路可走

最優(yōu)子結(jié)構(gòu):就是左邊和上面的數(shù)字和

重疊子問題:

如果直接設定邊界f(xy = 0) = 1,則會發(fā)生和例題中遞歸方法一樣的后果:
f(2,1)->f(1,1)+f(2,0)

f(1,2)->f(1,1)+f(0,2)

f(1,2) & f(2,1):HXD咱們一起走

所有數(shù)字將從1開始累加,顯然,時間復雜度很高

解決辦法也很簡單,從已知入手,一點點疊加,如圖所示.從左上角開始而不是從右下角反推

注意在這么推的時候,馬所控制的點無條件改為0即可,因為不可到達

我知道你很急,但你先別急??(一會有你急的)

常規(guī)開局,如果用萬能庫<bits/std++>也行,快讀快寫什么的當然更好,這里當個原始人(簡潔!(bushi))

聲明變量和函數(shù)

注意:只有全局變量會被初始化為默認值0,局部變量將會是隨機數(shù),是直接接手的原來的內(nèi)存而沒有調(diào)整.這一點需要有所注意

輸入數(shù)據(jù),沒啥好說的,等效于cin>>Bx>>By....這里為了對稱美觀

+1是為了直接取Bx,By方便,開long long 是為了防止數(shù)據(jù)量過大爆掉

Homo特有的無意義初始化

((i == Mx-2 || i == Mx+2) && (j == My-1 || j == My+1)) || ((i == Mx-1 || i == Mx+1) && (j == My-2 || j == My+2)) || (i == Mx && j == My)

這坨很長,但很簡單:判斷是不是馬所控制的九個點,這里只是傻乎乎得全列出來了而已

init相關(guān)的幾句是為了:如果初始化的路上有一個點是0,那后面的點必然全是0如

11111110(此時init為了)00000

一模一樣的y方向,不用看了,x改y就能跑

???

重頭戲來了,公式熟悉嗎,就是那個狀態(tài)轉(zhuǎn)移方程!(if內(nèi)是那一坨判斷??的玩意)

輸出,結(jié)束?(原代碼里還有一坨是遍歷這個二維數(shù)組的,對解題沒啥用)

對于一個15*15且沒有阻礙的方格,按照規(guī)定,有?155117520 種走法,直逼16E,再擴大一點int就會爆炸了.

P1004?累了,待會再寫....