如何优化暴力搜索

这个题目别看n和m只有100的范围，但是暴力算的话会超时，先看一下暴力的做法

#include<bits/stdc++.h>
using namespace std;

int n, m;
const int mo = (int)1e9 + 7;
int ans = 0;
// 规定1是店，2是花
void dfs(int dian, int hua,int jiu,int last) {
	if (dian > n || hua > m || jiu<0) return;
	if (dian == n && hua == m && jiu == 0&&last==2) {
		ans=(ans+1)%mo; return;
	}
	dfs(dian + 1, hua, jiu * 2,1);
	if (jiu) {
		dfs(dian, hua + 1, jiu - 1,2);
	}
}

int main() {
	cin >> n >> m;
	dfs(0, 0, 2,0);
	cout << ans;
	return 0;
}

不出意外会超时，我想着就记忆化搜索吧，但是发现，好像空间开不了那么大

int dp[105][105][1025][3];
// 规定1是店，2是花
int dfs(int dian, int hua,int jiu,int last) {
	if (jiu < 1025 && jiu >=0) {
		if(dp[dian][hua][jiu][last])  return dp[dian][hua][jiu][last];
	}
	//if (jiu<1025 && dp[dian][hua][jiu][last]) return dp[dian][hua][jiu][last];
	if (dian > n || hua > m || jiu<0) return 0;
	if (dian == n && hua == m && jiu == 0&&last==2) {
		ans=(ans+1)%mo; return 0;
	}
	return dfs(dian + 1, hua, jiu * 2, 1) + (jiu ? dfs(dian, hua + 1, jiu - 1, 2) : 0);
}

那现在还能怎么办，其实如果酒的数量大于花的数量，那么这个是无解 的

#include<bits/stdc++.h>
using namespace std;

#define int long long
int n, m;
const int mo = (int)1e9 + 7;
int ans = 0;
int dp[105][105][105];

int dfs(int dian, int hua, int jiu) {
	if (jiu > hua) return 0; // 酒大于花
	if (jiu < 0) return 0;// 酒变成负数了
	if (jiu == hua && dian != 0) return 0;
	if (dp[dian][hua][jiu] != -1) return dp[dian][hua][jiu];
	dp[dian][hua][jiu] = 0;
	if (dian) {
		dp[dian][hua][jiu] = dfs(dian - 1, hua, jiu * 2)%mo;
	}
	if (hua && jiu) {
		if (hua == 1 && jiu == 1) {
			dp[dian][hua][jiu] = (dp[dian][hua][jiu]+1)%mo;
		}
		else {
			dp[dian][hua][jiu] = (dp[dian][hua][jiu] + dfs(dian, hua - 1, jiu - 1))%mo;
		}
	}
	return dp[dian][hua][jiu];
}

signed main() {
	cin >> n >> m;
	memset(dp, -1, sizeof dp);
	int d = dfs(n, m, 2)%mo;
	cout << d;
	return 0;
}