動態規劃
動態規劃基礎
動態規劃將復雜問題分解成很多重疊的子問題，再通過子問題的解得到整個問題的解
分析步驟:
確定狀態:dp[i][j]=val,“到第i個為止，xx為j的方案數/最小代價/最大價值”
狀態轉移方程:
確定最終狀態
要求:
(1)最優子結構
(2)無后效性:已經求解的子問題，不會再受到后續決策的影響。
(3)子問題重疊，將子問題的解存儲下來
兩種思路:
(1)按題目
線性DP
數字三角形
學習:
(1)將整個大問題分解為一個小問題，就是a[i][j]位置肯定向max(a[i+1][j],a[i+1][j+1])的位置走，所以設置狀態dp[i][j]，表示從第i行第j列位置往下走的所有路徑的數字和的最大值,可以得到狀態轉移方程dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1])，然后自底向上遍歷，得到最終狀態dp[0][0]
代碼:
#include <bits/stdc++.h>using namespace std;const int N=105;
int n,a[N][N],dp[N][N];int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){cin>>a[i][j];}}for(int i=n-1;i>-1;i--){for(int j=0;j<=i;j++){dp[i][j]=a[i][j]+max(dp[i+1][j],dp[i+1][j+1]); //狀態轉移方程 }}cout<<dp[0][0];return 0;
}
破損的樓梯
學習:
(1)狀態dp[i]表示走到第i級臺階的方案數，可以有第i-1級臺階或者第i-2級臺階走到，所有得到狀態轉移方程dp[i]=dp[i-1]+dp[i-2]，得到最終狀態dp[n],不能從第n級臺階向下寫狀態轉移方程dp[i]=dp[i+1]+dp[i+2]，因為這樣你已經前提假設能走到第n級臺階了，不能走到的情況輸出0是錯誤的
代碼:
#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
const long long p=1e9+7;
int n,m,dp[N]; //狀態為從0級臺階走到第i級臺階的方案數
bool mark[N]; //損壞的臺階為true int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=0;i<m;i++){int t;cin>>t;mark[t]=true;}dp[0]=1;//第1級臺階特殊，只能從0級到達 if(!mark[1]) dp[1]=1;for(int i=2;i<=n;i++){//是破損臺階，跳過if(mark[i]) continue;//不是破損臺階，寫狀態轉移方程//第i級臺階可以由第i-1級臺階或者第i-2級臺階到達 //說明第i級臺階的方案數為第i-1級臺階的方案數加第i-2級臺階的方案數之和//破損臺階方案數為0 dp[i]=(dp[i-1]+dp[i-2])%p; }cout<<dp[n];return 0;
}
安全序列
學習思路1:
(1)此題跟上面不一樣，dp[i]表示以i結尾的方案和（這個思想可以學習），比如(1,4)是以4結尾的方案，而(0)就是全都不放的一種方案，所以狀態轉移方程為 d p [ i ] = ∑ j = 0 i ? k ? 1 d p [ j ] dp[i]=\sum_{j=0}^{i-k-1} dp[j] dp[i]=j=0∑i?k?1?dp[j]
,其中i-k-1>=0才要這樣轉移，例如k=2時，以4結尾的方案有(0,4)(1,4)，而不轉移的dp都是1，如(0),(1)，再利用前綴和優化 p r e f i x [ i ] = ∑ j = 0 i d p [ j ] prefix[i]=\sum_{j=0}^{i} dp[j] prefix[i]=j=0∑i?dp[j]
代碼:
#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=1e6+10,p=1e9+7;
int n,k;
ll dp[N],prefix[N]; //dp[i]表示以i結尾(最后一個放1的位置)的方案個數,狀態轉移方程為dp[i]=dp[0]+...+dp[i-k-1],所以需要前綴和prefix[i]=dp[0]+..+dp[i]
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;//以0結尾的方案個數為1(全不放，全為0) ,prefix[-1]無意義，所以要提前初始化dp[0]=prefix[0]=1;for(int i=1;i<=n;i++){//當i-k-1>=0時，才有狀態轉移,反之都是1 if(i-k-1<0) dp[i]=1;else dp[i]=prefix[i-k-1]; //不用減prefix[-1]prefix[i]=(prefix[i-1]+dp[i])%p;}cout<<prefix[n]; //結果不是dp[n],不是以n結尾的方案和，而是dp[0]+...+dp[n] return 0;
}
學習思路2:
(1)直接用dp[i]來表示共i個空位的方案和，而這一位可以放，也可以不放，方案和=第i位不放的方案+第i位放的方案，第i位不放的方案沒有限制條件，就是dp[i-1],而第i位放的方案與i-k-1和0的大小有關。如果i-k-1<0,說明不用考慮隔開k個位置的限制，放就是方案數+1，而如果i-k-1>=0，說明要考慮隔開k個位置的限制，方案數為dp[i-k-1]，分情況得到狀態轉移方程
代碼:
#include <bits/stdc++.h>using namespace std;typedef long long ll;
const int N=1e6+10,p=1e9+7;
int n,k;
ll dp[N]; //dp[i]表示共i個空位的方案和，等于該位置放+不放的方案和
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>k;dp[0]=1;for(int i=1;i<=n;i++){//當i-k-1<0時，放就是直接加1，不放就是dp[i-1], if(i-k-1<0) dp[i]=(dp[i-1]+1)%p;//當i-k-1>=0時，放的時候才要考慮dp[i-k-1]，才有意義，不放就是dp[i-1] else dp[i]=(dp[i-1]+dp[i-k-1])%p; }cout<<dp[n]; return 0;
}
二維DP
dp數組為二維,描述dp狀態的變量不止一個
擺花
學習:
(1)狀態dp[i][j]表示到第i種花為止(不一定以第i種花結尾，即不一定擺第i種花)，到第j位為止，擺花的方案，因為第i種花可以擺0-a[i]盆，所有dp[i][j]由dp[i-1][j-k],k=0-a[i]這些狀態轉移而來，相加,圖示:
![[擺花.png]]轉移方程為: d p [ i ] [ j ] = ∑ k = 0 k = a [ i ] a [ i ? 1 ] [ j ? k ] dp[i][j]=\sum_{k=0}^{k=a[i]}a[i-1][j-k] dp[i][j]=k=0∑k=a[i]?a[i?1][j?k]
注意初始狀態dp[0][0]=1,以及k<=min(j,a[i]),以及不用+=,因為要取模
代碼:
#include <bits/stdc++.h>using namespace std;
const int N=105,p=1e6+7;
int n,m,a[N],dp[N][N]; //dp[i][j]表示到第i種花為止，到第j位為止，擺花的方案數 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];//初始化dp[0][0]=1,不擺也是一種方案dp[0][0]=1;//狀態轉移方程 for(int i=1;i<=n;i++){ //從第1種花開始，到第n種花 for(int j=0;j<=m;j++){ //從第0位開始，到第m位//狀態轉移 int t=min(a[i],j); //第i種花最多擺放min(a[i],j]盆 for(int k=0;k<=t;k++){ //第i種花可以擺0-t盆 dp[i][j]=(dp[i][j]+dp[i-1][j-k])%p;//因為要取余，所有不用+= }}} cout<<dp[n][m];return 0;
}
選數異或
學習:
(1)這題跟擺花一樣，先區分一下子序列和子串的區別:
子序列不一定要求連續，而子串要求連續，兩個都要求順序跟原來一樣
dp[i][j]表示到第i個數字為止(不一定以第i個數字結尾，即子序列不一定包括第i個數字),到異或和值為j為止的子序列總數
狀態轉移方程就是第i-1個數字轉移到第i個數字，取第i個數字+不取第i個數字的和: d p [ i ] [ j ] = d p [ i ? 1 ] [ j ^ a [ i ] ] + d p [ i ? 1 ] [ j ] dp[i][j]=dp[i-1][j\verb|^|a[i]]+dp[i-1][j] dp[i][j]=dp[i?1][j^a[i]]+dp[i?1][j]
(2)dp[0][0]=1,因為空子序列的異或和是0，是一個子序列方案
(3)題目說0<=a[i]<63,根據異或性質，異或和不會超過63(63=2^6-1=111111),不管怎么異或都不會超過63，所有能開dp[N][70],j也能從0開始遍歷到70
代碼:
#include <bits/stdc++.h>using namespace std;const int N=1e5+10,p=998244353;
int n,x,a[N],dp[N][70]; //dp[i][j]表示到第i個數字為止(不一定以第i個數字結尾),到值為j為止的子序列個數 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>x;for(int i=1;i<=n;i++) cin>>a[i];//dp初始化,定義是空序列的異或和為0 dp[0][0]=1;for(int i=1;i<=n;i++){for(int j=0;j<70;j++){//狀態轉移，包括選第i個數和不選第i個數dp[i][j]=(dp[i-1][j^a[i]]+dp[i-1][j])%p;}} cout<<dp[n][x];return 0;
}
數字三角形
學習:
(1)這題跟線性DP的數字三角形有點不一樣，多了一個“向左下走的次數與向右下走的次數相差不能超過 1”的要求，所以自底向上dp狀態還要加上一個向右走的次數的維度,dp[i][j][k]表示在(i,j)位置向右走了k次的路徑最大和(通過最后狀態的k得到結果)，最后的狀態要對n分奇偶討論
代碼:
#include <bits/stdc++.h>using namespace std;const int N=105;
int n,dp[N][N][55],a[N][N]; //dp[i][j][k]表示在(i,j)位置向右走k次的路徑的數字和，相應的向左走的次數為n-i-k int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}for(int i=n;i>=1;i--){for(int j=1;j<=i;j++){//k從0到n-ifor(int k=0;k<=n-i;k++){//k>=1時，才能向右下走if(k>=1) dp[i][j][k]=a[i][j]+max(dp[i+1][j][k],dp[i+1][j+1][k-1]);//只能向左下走 else dp[i][j][k]=a[i][j]+dp[i+1][j][k];} }}//共走n-1次，分奇偶討論,保證向左下走的次數與向右下走的次數相差不能超過 1 //n-1為偶數，n為奇數，都一樣 if(n%2) cout<<dp[1][1][(n-1)/2];//n-1為奇數，n為偶數，取最大else cout<<max(dp[1][1][(n-1)/2],dp[1][1][n-1-(n-1)/2]);return 0;
}
(2)
學習:正因為有了"向左下走的次數與向右下走的次數相差不能超過 1"的要求，所有可以歸納出n為奇數最后走到(n,n/2+1)位置，而n為偶數，最后走到(n,n/2)或者(n,n/2+1)位置(結果位置已知)，所有可以直接自頂向下兩個維度得到答案，dp[i][j]表示在(i,j)位置的路徑最大和(仔細思考和原來題的區別)
代碼:
#include <bits/stdc++.h>using namespace std;const int N=105;
int n,dp[N][N],a[N][N]; //dp[i][j]表示在(i,j)位置路徑的數字和int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){cin>>a[i][j];}}//初始化 dp[1][1]=a[1][1];for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){//從上轉移到下 dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]; //是j-1 }} //n為奇數，就一個位置 if(n%2) cout<<dp[n][n/2+1];else cout<<max(dp[n][n/2],dp[n][n/2+1]);return 0;
}
LIS(最長上升子序列)
要點:
(1)子序列是指按原順序選出若干不一定連續的元素的子序列，LIS就是該子序列元素是依次遞增的，且長度最大。所以,對于固定的數組，雖然LIS序列不一定唯一，但LIS的長度是唯一的
(2)序列元素a[i]，狀態dp[i]表示以a[i]結尾的子序列的長度(包括a[i]),初始狀態都為1(自己本身),所以狀態轉移方程就是i>j,if a[i]>a[j],dp[i]=max(dp[i],dp[j]+1),例如:
id: 1 2 3 4 5 6 7 8
a[i]: 1 3 4 2 5 3 7 2
dp[i]: 1 2 3 2 4 3 5 2
從id轉移:默認 1 2 1 3 4 5 1
(3)目前只學O(n^2)的LIS，較難的之后再學
藍橋勇士
學習:
(1)典型的LIS問題，套模版即可
#include<bits/stdc++.h>using namespace std;const int N=1e3+10;
int n,a[N],dp[N],ans=-1;int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dp[i]=1;}for(int i=2;i<=n;i++){for(int j=1;j<i;j++){//戰力值超過則加if(a[i]>a[j]) dp[i]=max(dp[i],dp[j]+1);//選最長的 }ans=max(ans,dp[i]);}cout<<ans;return 0;
}
合唱隊形
學習:
(1)結果為左邊一個最長子序列，右邊一個最長子序列，中間i點截斷，所以不妨算dpl和dpr,最終枚舉i求得最大值
#include <bits/stdc++.h>using namespace std;const int N=105;
int n,a[N],dpl[N],dpr[N];//dpl為從左向右的LIS,dpr為從右向左的LIS,最終枚舉i,使得dpl[i]+dp[r]-1最大即可 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];dpl[i]=1;dpr[i]=1;}//先算dplfor(int i=2;i<=n;i++){for(int j=1;j<i;j++){if(a[i]>a[j]) dpl[i]=max(dpl[i],dpl[j]+1);}} //再算dprfor(int i=n-1;i>=1;i--){for(int j=n;j>i;j--){if(a[i]>a[j]) dpr[i]=max(dpr[i],dpr[j]+1);}} //最后枚舉i，算最終答案 int ans=-1;for(int i=1;i<=n;i++){ans=max(ans,dpl[i]+dpr[i]-1);//-1是因為i點算了2次 }cout<<n-ans;//ans為合唱隊員數量，結果為出列同學數量 return 0;
}
LCS(最長公共子序列)
學習:
(1)求兩個序列A，B的最長公共子序列，只有O(n^2)一種解法
(2)狀態dp[i][j]為A[1-i],B[1-j](不一定以a[i],b[j]結尾,即公共子序列不一定包括a[i],b[j])時的公共子序列長度,初始值為0,狀態轉移方程:
if a[i]=b[j] dp[i][j]=dp[i-1][j-1]+1; //相當于把公共元素加入公共子序列，長度加1
else dp[i][j]=max(dp[i-1],dp[j-1]) //相當于向后遍歷但不加入公共子序列，長度取最大的
最終狀態就是dp[n][m],例如:
A:1 3 4 2 5
B:1 4 3 6 2
dp:i:0 1 2 3 4 5
j:
0 0 0 0 0 0 0
1 0 1 1 1 1 1
2 0 1 1 2 2 2
3 0 1 2 2 2 2
4 0 1 2 2 2 2
5 0 1 2 2 3 3
最長公共子序列: 1 4 2
(3)求完dp數組，再回過來求最長公共子序列元素的方法:
從(n,m)開始回溯,直到跳出邊界停止
if a[i]=b[j] 說明從左上角來，回到(i-1,j-1),得到一個最長公共子序列元素
else 說明是從上方或者左側最大的方法而來if(dp[i-1][j]>=dp[i][j-1]) 回到(i-1,j)(=默認向上走)else 回到(i,j-1)
最長公共子序列
學習:
(1)模版題
代碼:
#include <bits/stdc++.h>
#include <algorithm>using namespace std;const int N=1e3+10;
int n,m,a[N],b[N],dp[N][N];
vector<int> v; //記錄最長公共子序列
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int j=1;j<=m;j++) cin>>b[j];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){//加入公共子序列 if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;//不加入 else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}cout<<dp[n][m]<<endl;//打印一個最長公共子序列int i=n,j=m; //起點while(i && j){//是最長公共子序列元素if(a[i]==b[j]){v.emplace_back(a[i]);i=i-1,j=j-1;}//不是else{if(dp[i-1][j]>=dp[i][j-1]) i=i-1;else j=j-1;} }//反轉v,為最長公共子序列元素順序reverse(v.begin(),v.end());for(auto &x:v){cout<<x<<" ";}return 0;
}
真題
接龍數列
學習:
(1)這題跟最長上升子序列(LIS)類似，只是判斷條件不同罷了，記住dp[i]是以a[i]結尾(不是到a[i]為止不包括a[i]那種)，但是只能拿到50分
(2)cin?從標準輸入讀取的數據最初都是以?字符序列?的形式存在的，具體是什么類型是自己定義轉換得來的，所以這題要獲得一個數字的首位和尾位，不用寫函數對整數操作，直接把數字當做一個字符串輸入，提取首位和尾位即可,不過記得減’0’:
string s;
cin>>s;
f[i]=s[0]-'0';
e[i]=s[s.size()-1]-'0';
代碼:
#include <bits/stdc++.h>using namespace std;
const int N=1e5+10;
int n,f[N],e[N],dp[N];//f數組記錄首位數字，e數組記錄末尾數字，dp[i]表示到第i個數字為止(以a[i]為結尾)，最長接龍數列的長度 int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++){string s;cin>>s;f[i]=s[0]-'0';e[i]=s[s.size()-1]-'0';dp[i]=1;}int maxn=1;for(int i=2;i<=n;i++){for(int j=1;j<i;j++){//狀態轉移 if(e[j]==f[i]){dp[i]=max(dp[i],dp[j]+1);}}maxn=max(maxn,dp[i]);}cout<<n-maxn;return 0;
}
優化學習:
(1)因為這題的條件就是把末位數字等與首位數字的兩個數字連接起來，本質上就是一個末位數字的狀態轉移到另一個末位數字的狀態,dp[i]表示以i數字結尾的最長接龍數列，因為數字為0-9，所以dp[10]即可，狀態轉移方程:
dp[b]=max(dp[b],dp[a]+1)(b為第i個數字的末位數字，a為第i個數字的首位數字，即前面某個數字的末位數字)
2023有獎問答
學習:
(1)dp填空題，dp[i][j]表示到第i題為止，到分數j為止的方案數，狀態轉移方程:
dp[i][0]=dp[i-1][0]+dp[i-1][10]+...+dp[i-1][90]
dp[i][j]=dp[i-1][j-10] //不用+1，因為表示方案數，狀態轉移過來這是一種方案,j>=10
(2)根據實際意義初始化dp:
dp[1][0]=dp[1][10]=1;//1道題只有0分和10分兩種狀態
代碼:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll dp[35][101];//dp[i][j]表示到第i題為止，到分數j為止的方案數 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//根據實際意義初始化 dp[1][0]=dp[1][10]=1;//1道題只有0分和10分兩種狀態ll ans=0;for(int i=2;i<=30;i++){//dp[i][0]轉移 for(int j=0;j<=90;j+=10){dp[i][0]+=dp[i-1][j];}//dp[i][j]轉移for(int j=10;j<=100;j+=10){dp[i][j]=dp[i-1][j-10];//不用+1，因為表示方案數，狀態轉移過來對于總體來看是一種方案 } }for(int i=1;i<=30;i++){ans+=dp[i][70];}cout<<ans;//ans=8335366return 0;
}
填空題暴力dfs代碼:
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
ll ans=0;//x為題目數量，y為分數
void dfs(int x,int y){//遞歸中止條件 if(y==100 || x>30) return;//x>30,x可以=30,此時y可能為70 if(y==70) ans++;//只要遇到70就加，當做中途放棄dfs(x+1,0);dfs(x+1,y+10);
}int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);dfs(0,0);cout<<ans;//ans=8335366return 0;
}
2022積木畫
學習:
(1)這題導致狀態轉移的原因是添加了一次積木(不一定是1個)，而積木又分I型和L型，所以當前狀態可以從添加I型積木前的狀態1和添加L型積木前的狀態2轉移過來(類似于爬樓梯)，當前狀態又可能出現兩行都有積木、第一行積木比第二行多一個、第二行比第一行多一個三種狀態(如何想的過程)，所以定義dp[i][j]表示到第i列為止，j=0,1,2分別表示三種狀態，的總方案數,狀態轉移如下圖所示
![[積木畫.png]]代碼:
#include <bits/stdc++.h>using namespace std;
const int N=1e7+10,p=1000000007;
int n,dp[N][3];//dp[i][j]表示到畫布第i列為止的方案數,j=0為第一行比第二行多一個,j=1表示兩行都一個,j=2表示第二行比第一行多一個 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n;//先初始化第1列和第2列 dp[1][1]=1,dp[2][0]=dp[2][2]=1,dp[2][1]=2;for(int i=3;i<=n;i++){//核心狀態轉移，表示添加I型積木或者L型積木轉移過來 //dp[i][0],即第i列第一行比第二行多一個dp[i][0]=(dp[i-1][2]+dp[i-2][1])%p;//dp[i][2],和dp[i][0]類似，反過來dp[i][2]=(dp[i-1][0]+dp[i-2][1])%p;//dp[i][1]比較特殊，添加兩種類型積木各有兩種轉移，分類討論dp[i][1]=( (dp[i-1][1]+dp[i-2][1])%p + (dp[i-1][0]+dp[i-1][2])%p)%p;//三個取余都不能少，位置也不能不對 }cout<<dp[n][1];return 0;
}
李白打酒加強版
學習:
(1)dp問題想好1.狀態2.狀態轉移方程3.什么條件下轉移哪些狀態(狀態的累加)4.最終狀態
![[李白打酒加強版1.png]]![[李白打酒加強版2.png]]
所以一共會有三種狀態轉移，而利用dp[i][j][k]=(dp[i][j][k]+某種狀態方案數)%p可以保證方案數是累加的
(2)本題要求最后一次必遇花，就是求dp[n][m-1][1],同時告訴你遍歷到m-1,且酒的量不超過m（因為只能減m*1升),且k>=1，因為最后一次要減1
(3)都從0開始遍歷，因為要賦只遇店的和只遇花的值，加上條件判斷控制狀態轉移即可，而不是給0賦一些值（自己考慮不周全），并從1開始遍歷(錯誤方法)
代碼:
#include <bits/stdc++.h>using namespace std;
const int p=1e9+7;
int n,m,dp[105][105][105];//dp[i][j][k]表示到遇店i次為止，遇花j次為止,酒k升為止的方案次數 int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>n>>m;dp[0][0][2]=1;for(int i=0;i<=n;i++){ //必須從0開始，因為i=0或者j=0有很多種情況 for(int j=0;j<=m-1;j++){ //遇花m-1次，最后一次必遇花 for(int k=0;k<=m;k++){ //因為最后要為0，遇花是減1，所以酒的大小不會超過m //遇店 if(i>=1 && k%2==0) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k/2])%p;//遇花(方案累加,加上dp[i][j][k]，如果前面遇店，就等價于加上遇店) if(j>=1 && k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i][j-1][k+1])%p; //k>=1,因為最后一次是遇花，k必須大于等于1/* //等價于下面的方法//遇店 if(i>=1 && k%2==0) dp[i][j][k]=dp[i-1][j][k/2];//遇花if(j>=1 && k>=1) dp[i][j][k]=dp[i][j-1][k+1]; //k>=1,因為最后一次是遇花，k必須大于等于1//遇店+遇花if(i>=1 && k%2==0 && j>=1 && k>=1) dp[i][j][k]=(dp[i-1][j][k/2]+dp[i][j-1][k+1])%p;*/}}}cout<<dp[n][m-1][1];//保證最后一次是花，就是求dp[n][m-1][1] return 0;
}
dfs+記憶化+剪枝:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 7;
const int mod = 1e9 + 7;
int dp[maxn][maxn][maxn];
int dfs(int x, int y, int z) // 酒量、遇見店次數、遇見花次數
{if (x < 0 || y < 0 || z < 0) return 0; // 不合法if (x > z) return 0; // 酒量不可能大于剩余"遇見花的次數"if (z == 1) return y == 0 && x == 1; // 最后一次必須遇到的是花 && 酒量只剩1if (dp[x][y][z] != -1) return dp[x][y][z];dp[x][y][z] = (dfs(x * 2, y - 1, z) + dfs(x - 1, y, z - 1)) % mod;return dp[x][y][z];
}
int main()
{memset(dp, -1, sizeof dp);int n, m; cin >> n >> m;cout << dfs(2, n, m) << endl;return 0;
}
