题目描述
小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共 m 盆。通过调查顾客的喜好，小明列出了顾客最喜欢的 n 种花，从 1 到 n 标号。为了在门口展出更多种花，规定第i种花不能超过 a[i] 盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。
试编程计算，一共有多少种不同的摆花方案。
一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对 10^6+7 取模的结果。
样例输入
2 4
3 2
样例输出
2
动态规划
#include <bits/stdc++.h>
using namespace std;
const int N=105, mod=1e6+7;
int n,m;
int a[N];
int f[N][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0][0]=1; //什么都不选时一种方案 因此初始化为1
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
for(int k = 0; k <= min(j,a[i]); k++){
f[i][j]=(f[i][j]+f[i-1][j-k]) % mod;
}
cout<<f[n][m];
return 0;
}
滚动数组
#include <bits/stdc++.h>
using namespace std;
const int N=105, mod=1e6+7;
int n,m,t;
int a[N];
int f[2][N];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
f[0][0]=1; //一个都没选的也是一种方案
for(int i=1;i<=n;i++){
t=1-t; //实现滚动 t 一开始初始化为 0 通过赋值得 1
for(int j=0;j<=m;j++){
f[t][j]=0; //初始化 -- 改成下一个状态
for(int k=0;k<=min(a[i],j);k++){
f[t][j]=(f[t][j]+f[1-t][j-k])%mod;
}
}
}
cout<<f[t][m];
return 0;
}