题外废话：
真的超级喜欢这道题
yy一提醒，我发现这道题和【洛谷p2089】 烤鸡有异曲同工之妙（数据更大了更容易TLE呢qwq）
SOLUTION1：（暴搜）
搜索：关于搜索就不用多介绍了吧，这里是用了dfs：dfs函数中有两个变量，rest和i分别表示还需要摆放多少盆花以及现在摆放到第几种花了，因为我们是从0开始枚举，因此如果某种花我们不选择，那就可以看做这种花选择了0盆；
几个返回条件：
1.rest==0时，记录ans++（ans是全局变量）return，不需要满足rest==0&&i=n+1（因为只要rest被枚举完了就可以了，后面的花不摆放就好啦）
2.i==n+1时，return；为什么是i=n+1呢，因为当i=n时，我们并没有枚举第n种花摆放的盆数，如果现在就返回，显然是会对结果造成很大的影响，进而影响整个结果；
3.rest<0时，return；因为此时所有m盆花已经被摆出去了，没有继续搜索的必要，直接return；
核心语句：
其实就一句话：
for(int j=;j<=a[i];j++)
dfs(rest-j,i+);
直接暴力dfs因为实际并没有改变rest和i的值，所以我们连回溯都不需回溯；
以下是完整CODE：
CODE1：
#include<bits/stdc++.h> using namespace std; int n,m,ans,cnt;
int a[],b[]; void dfs(int rest/*还需要摆多少盆花*/,int i/*n种花*/){
if(rest==){
ans++;ans%=;
return;
}
if(i==n+) return;
if(rest<) return;
for(int j=;j<=a[i];j++)
dfs(rest-j,i+);
return;
} int main(){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
dfs(m,);
cout<<ans<<endl;
}
但是非常遗憾的是暴搜显然不是正解，成功的TLE了7个点（功成身退）
所以我们想到了记忆化搜索：
SOLUTION2：（记忆化搜索）
写暴搜的原因是因为并不会正解DP，因此只好暴搜了，然后又知道暴搜妥妥的TLE，所以在暴搜代码完成之后，改成了记忆化：
大致思路还是没有变，但dfs从没有返回值变成了带有返回值的dfs，当rest==0时（形成一种摆花条件时）return 1；否则return 0（对于最小子问题）；对于每一次定义一个ans（当然也可以开全局然后每次重新赋值），枚举所有的摆花盆数，ans+=dfs（rest-j,i+1）[意思是对于某种花枚举所有可能的摆放盆数，统计剩余的空位置的总方案数，表示某种花摆j盆的总方案数（可能有点不对是非常绕）]，记忆化数组b[i][rest]表示第i种花摆放前剩余rest个空位置（没有摆花）剩余rest个位置摆花的方案数，当我们已经计算过这个方案数以后，就可以直接拿来用而不是总是递归炸掉了。所以加一句
if(b[i][rest]) return b[i][rest];
如何计算b[i][rest]以及每一步的ans：
其实楼上两个东西是一回事，b[i][rest]=ans;
下面来看如何计算ans：首先枚举第i种花所有摆放盆数（0~a[i]），然后dfs（rest-j,i+1），不断将求得的值加到ans里，（ans记录的是当前要摆第i种花，此时还剩rest（第i种花还没摆）个位置时所有摆花的方案数）不要忘记取mod；
最后不要忘记return ans；
CODE2:
#include<bits/stdc++.h> using namespace std; long long n,m,cnt;
long long a[],b[][];
const int mod=; long long dfs(long long rest/*还需要摆多少盆花*/,long long i/*摆放n种花*/){
if(rest==)
return ;
if(i==n+) return ;
if(rest<) return ;
if(b[i][rest]) return b[i][rest];
int ans=;
for(int j=;j<=a[i];j++){
if(rest-j<) break;
ans=(ans+dfs(rest-j,i+))%mod;
}
b[i][rest]=ans;
return ans;
} int main(){
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++)
scanf("%lld",&a[i]);
cout<<dfs(m,)%mod<<endl;
}
悄咪咪的粘上记忆化搜索的模板：（来自oi-wiki）
int g[MAXN];
int f(传入数值) {
if (g[规模] != 无效数值) return g[规模];
if (终止条件) return 最小子问题解;
g[规模] = f(缩小规模);
return g[规模];
}
int main() {
... memset(g, 无效数值, sizeof(g));
...
}
SOLUTION3：（正解-动态规划）
q姓神仙的题解【题解】
定义二维数组f[i][j]表示摆放i种花共j盆的最大方案数，初始状态是：f[i][0]=1；（因为不管是哪种花，只要不摆放，方案数均为1）这里虽然是二位数组，但DP时需要三重循环第一重循环i表示摆放i种花，第二重循环j表示这i种花共摆放多少盆（显然是1~m），第三重循环k，表示的是这种花摆放的盆数，（从0盆到a[i]盆），这里的第三层循环要从j到j-a[i]进行枚举转移方程就是f[i][j]+=f[i-1][k]%mod：
啥意思：
因为前i种花一共摆放j盆，那么假设第i种花摆放k1（k1∈（0，a[k1]）盆，那么前面的i-1种花就摆放j-k1盆（所以第三层循环枚举的是前i-1种花摆放的方案数），那么所有的方案数相加就是摆放i种花j盆的最大方案数；
最后的答案就是f[n][m]%mod；（最后要%mod防止超出答案）
CODE3:
#include<bits/stdc++.h> using namespace std; int n,m;
int a[],f[][];
const int mod=; int main(){
cin>>n>>m;
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++) f[i][]=;
for(int i=;i<=n;i++)//have n flower
for(int j=;j<=m;j++)//set out how many flower in total
for(int k=j;k>=j-a[i];k--) {//each flower set out how many
if(k<)break;
f[i][j]+=f[i-][k]%mod;
}
cout<<f[n][m]%mod;
}
真.end-