题解 | 【模板】记忆化搜索

#include<bits/stdc++.h>
using namespace std;
const int N=200,MOD=1e9+7,INF=0x3f3f3f3f;

int dp[N][N][N];
int T,a,b,c;

int dfs(int x,int y,int z){
	if(dp[x][y][z]!=INF) return dp[x][y][z];
	if(x<=0||y<=0||z<=0) return dp[x][y][z]=1;
	else if(x<y&&y<z) return dp[x][y][z]=((dfs(x,y,z-1)+dfs(x,y-1,z-1))%MOD-dfs(x,y-1,z)+MOD)%MOD;
	else return dp[x][y][z]=(((dfs(x-1,y,z)+dfs(x-1,y-1,z))%MOD+dfs(x-1,y,z-1))%MOD-dfs(x-1,y-1,z-1)+MOD)%MOD;
}

void solve(){
		
	int res=dfs(a,b,c);
	
	cout<<res<<endl;
	return;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	memset(dp,0x3f,sizeof(dp));
	
	cin>>T;
	while(T--){
		cin>>a>>b>>c;
		solve();
	}
	
    return 0;
}