可以把4维用滚动数组优化,找到状态转移方程就不难了
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=110,mod=1e9+7,M=2*N;
int n,m;
ll dp[M][N][N][2];//第i天,遇到了j次店,还剩k酒的次数 // 0 x2 1 -1;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m; //n店 m酒
// dp[0][0][2][0]=1;
dp[0][0][2][1]=1;
for(int i=1;i<=n+m;i++){
for(int j=0;j<=n;j++){
for(int k=0;k<=m;k++){
// 处理今天是 0的情况
if(j-1>=0&&k%2==0)
dp[i][j][k][0]+=(dp[i-1][j-1][k/2][0]+dp[i-1][j-1][k/2][1])%mod;
// 处理今天是 1的情况
dp[i][j][k][1]+=(dp[i-1][j][k+1][0]+dp[i-1][j][k+1][1])%mod;
}
}
}
cout << dp[n+m][n][0][1];
}