有n个位置，每个位置最多可以放a[i]个物品，现在你有m个物品想要全部放到位子上，求共有多少种放法？

设dp[i][j] 为前i个位置放了j个物品的方案数

然后我们可以想到枚举位置;
然后在枚举前面一共放了多少个物品;
在枚举当前位置放多少个物品
代码：复杂度为O(n * m ^ 2) 很明显超时

for(int i = 1; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        for (int k = 0; k <= a[i]; k++) {
        dp[i][j] += dp[i - 1][j - k];
        }
    }
}

很明显枚举放了多少个物品是可以用前缀和优化的

#include <bits/stdc++.h>
#include <iostream>
#include <string.h>
#include <math.h>

using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
int dp[105][maxn], a[maxn];
int sum[maxn];

int main() {
//    freopen("in.in", "r", stdin);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dp[1][0] = 1; sum[0] = 1;
    for (int i = 1; i <= a[1]; i++) {
        dp[1][i] = 1; sum[i] = sum[i -1] + dp[1][i];
    }
    for (int i = 1; i <= m; i++) {
        sum[i] = sum[i - 1] + dp[1][i];
    }
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (j > a[i]) { //前缀和优化
                dp[i][j] = (sum[j] - sum[j - a[i] - 1] + mod) % mod;
            } else {
                dp[i][j] = sum[j];
            }
        }
        sum[0] = dp[i][0];
        for (int j = 1; j <= m; j++) sum[j] = (sum[j - 1] + dp[i][j]) % mod;

    }
    cout << dp[n][m] << endl;
    return 0;
}