记忆化搜索
因为在搜索的时候我们发现,对于i,j如果相同,那么他们后面的方案数也一定相同,省去了重复搜索
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, mod = 1000007;
int n, m, a[N], state[N][N];
int dfs(int u, int sum)//选第几个物品,当前的和是多少
{
int res = 0;
if(sum == m) return 1;
if(sum > m || u > n) return 0;
if(state[u][sum]) return state[u][sum];
for(int i = 0; i <= min(a[u], m - sum); i ++)//枚举数量
res = (res + dfs(u + 1, sum + i)) % mod;
state[u][sum] = res;//记录状态
return res;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> a[i];
cout << dfs(1, 0) << endl;
return 0;
}
dp
把每个种类的花看成一个物品,那么就是多重背包问题求装满背包方案数
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 110, mod = 1000007;
int f[N], n, m;
int main()
{
cin >> n >> m;
f[0] = 1;
for(int i = 1; i <= n; i ++)//枚举物品
{
int v;
scanf("%d", &v);
for(int j = m; j >= 0; j --)//枚举体积
for(int k = 1; k <= min(v, j); k ++)
f[j] = (f[j] + f[j - k]) % mod;
}
cout << f[m] << endl;
return 0;
}