學習qzz的命名,來寫一篇關于動态規劃(dp)的入門部落格。
動态規劃應該算是一個入門oier的坑,動态規劃的抽象即神奇之處,讓很多萌新 萌比。
寫這篇部落格的目标,就是想要用一些容易了解的方式,講解入門動态規劃的真正意義。
奶萌兔的溫馨提示:建議先了解dfs哦~(本文以一種較為新奇的方式解釋DP)
動态規劃
那什麼是動态規劃?
來問問神奇的奶萌兔吧(強行盜梗)!
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL5kDO4UDO0ETOx0SOwMzM1ADNxIDNwcDM4EDMy0iN4gTN4ATMvw1NwgTMwIzLcZDO4UDOwEzLcd2bsJ2Lc12bj5ycn9Gbi52YugTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
(奶萌兔來給你講解啦~雖然還在睡覺=w=)
動态規劃(英語:Dynamic programming,簡稱DP)是一種在數學、管理科學、計算機科學、經濟學和生物資訊學中使用的,通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。
動态規劃常常适用于有重疊子問題[1]和最優子結構性質的問題,動态規劃方法所耗時間往往遠少于樸素解法。
動态規劃背後的基本思想非常簡單。大緻上,若要解一個給定問題,我們需要解其不同部分(即子問題),再根據子問題的解以得出原問題的解。
通常許多子問題非常相似,為此動态規劃法試圖僅僅解決每個子問題一次,進而減少計算量:一旦某個給定子問題的解已經算出,則将其記憶化存儲,以便下次需要同一個子問題解之時直接查表。
這種做法在重複子問題的數目關于輸入的規模呈指數增長時特别有用。----來自wiki百科
說這麼多,DP能幹什麼?
奶萌兔的回答:解決一些問題...解決一些,dfs效率無法通過的問題。
不如先講一道例題:
例1
爬樓梯:現在有n層樓梯,奶萌兔位于第0層 現在奶萌兔每一次可以往上爬1層或者2層,問奶萌兔爬到第n層有多少種方案?
這是一道經典的入門題,對于這道題,我們由簡入深。
如何dfs?
這樣考慮 dfs(int dep) 表示奶萌兔在第dep層。
那有兩個走法,一個是dfs(dep+1) 一個是dfs(dep+2)。
而dfs的邊界呢? 則是 n 。 即 if (dep>n) return;
初始值? dfs(0) 從第0層開始。
對于答案的統計? 那就是每當dep為n時,說明到達了對ans統計加1。 即 if (dep==n) ans++ 且return;
說了怎麼多dfs?對dp有個什麼用啊!!!
這時候,奶萌兔來引入一個東西——狀态。
狀态是什麼?用淺顯易懂的解釋就是,dfs需要儲存的東西(不一定...),如dfs(int dep) dep(奶萌兔目前的層數)就是一個狀态。
而dp則是利用狀态之間的互相關聯,答案得以更新。
那下面,來講 如何dp?
這樣考慮 DP[dep] 表示奶萌兔從第0層走到第dep層時的方案數
依舊有兩個走法,一個是DP[dep+1] 一個是DP[dep+2]。
是不是和dfs很相似? 接下來是重點。
初始值 dp[0]=1 到第0層有一種方案,就是一開始就在0層。
DP[dep+1] DP[dep+2]會等于什麼?
DP[dep+1]+=DP[dep] DP[dep+2]+=DP[dep]
因為走到第dep層的方案是DP[dep],那麼在走一層的時候,就隻能走到dep+1的地方,那麼dep上的全部方案,在通過走一步這樣唯一的一個方法,可以到達dep+1,是以走到dep+1包含了dep上的方案,dep+2同理。
上面的兩個式子就是狀态轉移方程了。
簡單的轉化一下, dp[dep+1]+=dp[dep] dp[dep+2]+=dep[dep] 則dp[dep]=dp[dep-1]+dp[dep-2] (當然不轉化也是可以的,但對于部分題目,一些轉化之後可能可以是以優化效率)
例2
從一個一維的題目,試試跳到二維。
騎士周遊:第一問可以直接往字典序最小去dfs,是以直接關注第二問吧
第二問:給一個n*m的棋盤
,給定起點x1,y1 終點 x2,y2 在隻能走日且隻能向右走的情況下,問方案數。
這是例1的拓展,從一維的向上走,變為二維的向右走。
首先對于這樣的棋盤,我們是不習慣的,因為與我們的數組順序不同,讓人煩心。
那怎麼辦捏?問問神奇的奶萌兔!
奶萌兔幽幽的說了一句:對~稱~旋~轉~
哈!這是原來的題
哈!這還是原來的題
于是旋轉一下之後,棋盤還是原來的棋盤,隻是方向改變了。
題目就變成了隻走日字且向下走的情況。
老規矩呢,如何dfs?
用用新名詞,狀态,dfs的狀态是什麼? dfs(int x,int y) 表示目前奶萌兔騎士在(x,y)的位置。
那就是有四個走法
dfs(x+1,y+2) dfs(x+2,y+1) dfs(x+1,y-2) dfs(x+2,y-1)
邊界 0 ,n 0 ,m 即 x>0且x<=n y>0且y<=m
初始:dfs(x1,y1)
答案的統計:每當 x==x2&&y==y2 時說明到終點了,那ans++
dp類比就好啦,狀态就是數組的下标。
DP[x][y] 表示奶萌兔騎士從(x1,y1)出發到(x,y) 的位置時的方案。
一樣四個走法
DP[x+1][y+2] DP[x+2][y+1] DP[x+1][y-2] DP[x+2][y-1]
邊界是一樣的哦~
初始:DP[x1][y1]=1 (在起點的時候就是一個方案)
答案:DP[x2][y2]
那轉移方程,和例1一樣哦,隻是拓展為二維,走法變多一些。
DP[x+1][y+2]+=DP[x][y] DP[x+2][y+1]+=DP[x][y] DP[x+1][y-2]+=DP[x][y] DP[x+2][y-1]+=DP[x][y]
簡單轉化一下: dp[x][y]=dp[x-1][y-2]+dp[x-2][y-1]+dp[x-1][y+2]+dp[x-2][y+1];
好了問題來了:怎麼轉化的? 不妨這樣撕烤,固定住(x,y) 找找哪些點能到(x,y) 那些點的方案數加起來就是了(或者,對前面的方程變化,x+d改為x-d,y+d改為y-d (d為常數))。
1 #define ll long long
2 #include<cstdio>
3 #include<iostream>
4 using namespace std;
5 ll f[100][100];
6 int ansx[100],ansy[100];
7 int n,m,x1,x2,y1,y2;
8 const ll HR=1e18;
9 void dfs(int dep,int nowx,int nowy){
10 ansx[dep]=nowx;
11 ansy[dep]=nowy;
12 if (nowx==n&&nowy==m) {
13 for (int i=1;i<dep;i++)
14 printf("(%d,%d)-",ansx[i],ansy[i]);
15 printf("(%d,%d)",ansx[dep],ansy[dep]);
16 exit(0);
17 }
18 //dfs的順序注意按字典序最小。
19 if (nowx+1<=n&&nowy-2>0) dfs(dep+1,nowx+1,nowy-2);
20 if (nowx+1<=n&&nowy+2<=m) dfs(dep+1,nowx+1,nowy+2);
21 if (nowx+2<=n&&nowy-1>0) dfs(dep+1,nowx+2,nowy-1);
22 if (nowx+2<=n&&nowy+1<=m) dfs(dep+1,nowx+2,nowy+1);
23 }
24 int main(){
25 scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
26 if (x1==0) {
27 dfs(1,1,1); //第一問
28 printf("NO");
29 return 0;
30 }
31 //第二問
32 f[x1][y1]=1;
33 for (int i=x1+1;i<=x2;i++){ //從x1+1開始,因為x1這一行是不可能更新的。
34 for (int j=1;j<=m;j++){
35 if (j-2>0) f[i][j]+=f[i-1][j-2]; //邊界
36 f[i][j]%=HR;
37 f[i][j]+=f[i-1][j+2];
38 //為什麼這個不判?原因是f[i-1][j+2]的值一定是0,因為無法更新到邊界外的數,而初始值都是0,注意把數組開大即可,下面同理
39 f[i][j]%=HR;
40 f[i][j]+=f[i-2][j-1];
41 f[i][j]%=HR;
42 f[i][j]+=f[i-2][j+1];
43 f[i][j]%=HR;
44 }
45 }
46 printf("%lld",f[x2][y2]);
47 return 0;
48
49 }
例2
以上就是入門的方案數dp。
後期可能更新其他dp呀~
轉載于:https://www.cnblogs.com/Bunnycxk/p/9265901.html