一位蒟蒻的第一个记忆化搜索代码

071maozihan 2022-04-06 18:59:25 30 返回题目

#include<bits/stdc++.h>

#define int long long

const long long maxn=1e3+10,P=1e9+7;

using namespace std;

int dp[maxn][maxn];

int n,ans;

int f(int x,int a,int b){

if(dp[a][b]!=0)return dp[a][b];//标记记忆化

if(x==0||a==0||b==0)return 1; //特判

if(x==1)return 1;//特判*2

if(a>b)return 0;//判断不合法情况

int cnt=0;

for(int i=a;i<=b;i++){

cnt+=f(b,i,b-i);//将b分解为 i和b-i继续计算

cnt%=P;//取模

} dp[a][b]=cnt;//记忆化赋值

return cnt;//返回值

}

signed main()

{

cin>>n;

for(int i=1;i<=n;i++){

ans+=f(n,i,n-i);//将n分解为 i与n-i

ans%=P;

}

cout<<ans;

return 0;

}

{{ vote && vote.total.up }}