Gọi ~dp[i][j]~ là số cách chia ~j~ viên kẹo cho ~i~ đứa trẻ đầu tiên.

Ta có:

Độ phức tạp tính toán: ~O(N\cdot K^2)~.

Nếu áp dụng công thức trên thì ta phải sử dụng mảng hai chiều để lưu trữ tuy nhiên để tính dòng ~i~ ta chỉ cần dòng ~i-1~.

Như vậy, gọi ~dp[j]~ là số cách chia ~j~ viên kẹo cho ~i~ đứa trẻ đầu tiên và ~dq[j]~ là số cách chia ~j~ viên kẹo cho ~i-1~ đứa trẻ đầu tiên. Sau khi tính toán xong ta chỉ cần lưu mảng ~dp~ vào mảng ~dq~.

Nhận thấy ~dp[j]~ nhận giá trị là tổng từ ~dq[j-a_i]~ tới ~dq[j]~. Chính vì thế mà với mỗi ~dp[j]~ chúng ta phải duyệt lại từ ~j-a_i~ tới ~j~ khiến cho chi phí tính toán cao.

Ta có thể giải quyết vấn đề trên bằng cách tạo thêm mảng ~S~, với ~S_j = dq[0] + dq[1] + dq[2] + ... + dq[j]~. Mảng ~S~ gọi là mảng cộng dồn.

Khi đó, ta có thể tính ~dp[j] = S[j] - S[j-a_i-1]~.Chínhh vì không cần phải duyệt lại nữa mà độ phức tập tính toán giảm còn ~O(N\cdot K)~.

#include <bits/stdc++.h>

using namespace std;

const int MAXK = 100000;
const int MOD = 1000000007;

int add(int i, int j) {
    if ((i += j) >= MOD)
        i -= MOD;
    return i;
}

int sub(int i, int j) {
    if ((i -= j) < 0)
        i += MOD;
    return i;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n, k, a;
    cin >> n >> k;

    static int dp[MAXK + 1], dq[MAXK + 1];
    dp[0] = 1;
    for (int i = 1; i <= n; ++i) {

        cin >> a;

        for (int j = 1; j <= k; ++j)
            dp[j] = add(dp[j - 1], dp[j]); 
        for (int j = 0; j <= k; ++j)
            dq[j] = sub(dp[j], (j > a ? dp[j - a - 1] : 0));
        swap(dp, dq);
    }
    cout << dp[k] << '\n';
}