摆花

暴力搜索

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000 + 7;
int n, m, ans;
int a[105];
// 当前考虑第now种话摆几盆，之前已经摆了sum种花
void dfs(int now, int sum)
{
    if (sum == m)
    {
        ans++;
        ans %= MOD;
        return;
    }
    if (now > n)
        return;
    // 考虑当前这种花摆几盆
    for (int i = 0; i <= min(a[now], m - sum); i++)
        dfs(now + 1, sum + i);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    ans = 0;
    dfs(1, 0);

    cout << ans << "\n";
    return 0;
}

三重循环

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000 + 7;
int n, m, ans;
int a[105];
int dp[105][105]; // dp[i][j]: 前i种花摆j盆的方案数
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0, sizeof(dp)); // 0种方案表示无解
    // 前0种花摆0盆，有什么都不摆这种方案，前0种花摆其他的盆数都是无解的
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = 1; // 什么都不摆也是一种方案
        for (int j = 1; j <= m; j++)
        {
            // 决策：考虑第i种花摆几盆（k盆）
            for (int k = 0; k <= min(a[i], j); k++)
            {
                // 第 i 种花摆了 k 盆时，需要前 i-1 种花摆 j-k 盆
                dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % MOD;
            }
        }
    }
    cout << dp[n][m] << "\n";
    return 0;
}

前缀和优化

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000 + 7;
int n, m, ans;
int a[105];
int dp[105][105];  // dp[i][j]: 前i种花摆j盆的方案数
int sum[105][105]; // sum[i][j]: dp[i][0]~dp[i][j] 之和
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    memset(dp, 0, sizeof(dp)); // 0种方案表示无解
    // 前0种花摆0盆，有什么都不摆这种方案，前0种花摆其他的盆数都是无解的
    dp[0][0] = 1;
    for (int i = 0; i <= m; i++)
        sum[0][i] = 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = 1; // 什么都不摆也是一种方案
        for (int j = 1; j <= m; j++)
        {
            // 决策：考虑第i种花摆几盆（k盆）
            int L = j - min(a[i], j);
            int R = j - 0;
            // dp[i][j] = sum(dp[i-1][L] ...... dp[i-1][R])
            if (L == 0)
                dp[i][j] = sum[i - 1][R];
            else
                dp[i][j] = sum[i - 1][R] - sum[i - 1][L - 1];
            dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
        }
        // 处理dp第i行的前缀和
        sum[i][0] = dp[i][0];
        for (int j = 1; j <= m; j++)
            sum[i][j] = (sum[i][j - 1] + dp[i][j]) % MOD;
    }
    cout << dp[n][m] << "\n";
    return 0;
}