题解:
摆花 状态转移方程:f[i][j]+=f[i-1][j-k] 状态摆第i种花 还可摆j盆时的方案数
#include<bits/stdc++.h>
using namespace std;
const int N=101;
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;// 初始化
for(int i=1;i<=n;i++)//遍历每一种花
{
for(int j=0;j<=m;j++)//防止越界
for(int k=0;k<=min(a[i],j);k++)// if 第i种花的数量>现在可摆花的总量 以现在可摆花的总量作为 k 的边界
f[i][j]=(f[i-1][j-k]+f[i][j])%1000007;
}
cout<<f[n][m];
return 0;
}
类似于背包的优化
#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[101];
int a[101];
int main()
{
//依然是非常正常的输入
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
f[0]=1; // 初始化
//dp
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=min(a[i],j);k++)
{
f[j]=(f[j]+f[j-k])%1000007;
}
}
}
cout<<f[m];
return 0;
}