我们用 $dp_{i,j}$ 表示进行完第 $i$ 人时，用了 $j$ 个糖果。 则答案表示为 $dp_{n,k}$。当进行到第 $i$ 个人时，可以分得 $0$ ~ $a_i$ 个糖果，遍历前 $i-1$ 个人的情况数，寻找符合当前要求的情况。

则状态转移方程为

初步代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10,K=1e5+10,P=1e9+7;
int k,n,a[N];
long long dp[N][K];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			for(int p=max(0,j-a[i]);p<=j;p++){
				dp[i][j]=(dp[i][j]+dp[i-1][p])%P;
			}
		}
	}
	printf("%lld\n",dp[n][k]);
	return 0;
}

这种做法是 $O(NK^2)$ ，会 $\color{#F5E53A}{TLE}$ ，考虑优化。

因为 $dp_{i,j}$ 求的是一段连续的区间的和，所以可以使用前缀和预处理，使得 $sum_i=\sum_{j=0}^{i} dp[i-1][j]$ 。

该思路时间复杂度为$O(NK)$

优质代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10,K=1e5+10,P=1e9+7;
#define getsum(l,r) (l==0?sum[r]:((sum[r]-sum[l-1]+P)%P))
int k,n,a[N];
long long dp[N][K],sum[K];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		sum[0]=dp[i-1][0];
		for(int j=1;j<=k;j++)
			sum[j]=(sum[j-1]+dp[i-1][j])%P;
		for(int j=0;j<=k;j++)
			dp[i][j]=getsum(max(0,j-a[i]),j);
	}
	printf("%lld\n",dp[n][k]);
	return 0;
}

已经$\textcolor{#1AD914}{AC}$了，但我们希望追求更极致的完美。该程序的空间复杂度为 $O(NK)$ ,我们可以用滚动优化，使空间复杂度降为 $O(N+K)$ 。

终极代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+10,K=1e5+10,P=1e9+7;
#define getsum(l,r) (l==0?sum[r]:((sum[r]-sum[l-1]+P)%P))
int k,n,a[N];
long long dp[K],sum[K];
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	dp[0]=1;
	for(int i=1;i<=n;i++){
		sum[0]=dp[0];
		for(int j=1;j<=k;j++)
			sum[j]=(sum[j-1]+dp[j])%P;
		for(int j=0;j<=k;j++)
			dp[j]=getsum(max(0,j-a[i]),j);
	}
	printf("%lld\n",dp[k]);
	return 0;
}

OK，看到N<=100,K<=1e5 已经可以想出时间复杂度肯定是O(NK)了。这里直接给思路：

状态设计： dp[i][j]表示进行到第i人时，已经用了j个糖果。 答案：dp[n][k]

转移方程： dp[i][j]=∑(p=max(0,j-a[i]),j)dp[i][p]

注意到这种做法是O(NK^2)，考虑优化

又注意到dp[i][j]求的是一段连续的区间的dp和，可以使用前缀和优化：在转移前预处理出dp[i-1]的前缀和，对于每个dp[i][j]，加上sum[j]-sum[max(0,k-a[i])-1]即可。

注意0需要特判，时间为O(NK)，能过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e2+10,M=1e5+10,mod=1e9+7;
int k,n,a[N],dp[N][M],sum[M];
int gs(int l,int r){return (l==0?sum[r]:(sum[r]-sum[l-1]+mod)%mod);}
signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		sum[0]=dp[i-1][0];
		for(int j=1;j<=k;j++)sum[j]=(sum[j-1]+dp[i-1][j])%mod;
		for(int j=0;j<=k;j++)dp[i][j]=gs(max(0ll,j-a[i]),j);
	}
	printf("%lld\n",dp[n][k]);
	return 0;
}

问题：子集总和方案数（每个元素最多选一次）

思路：动态规划，dp[i][j]表示前i个元素总和为j时的方案数。通过前缀和优化转移，降低时间复杂度。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD = 1e9 + 7;
int n, m, a[105];
ll dp[105][100005], sum[100005];

ll getsum(int l, int r) { // 前缀和查询
    return (l == 0 ? sum[r] : (sum[r] + MOD - sum[l - 1]) % MOD);
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    dp[0][0] = 1; // 初始状态: 前0个元素，总和0的方案数为1
    for (int i = 1; i <= n; i++) {
        sum[0] = dp[i - 1][0]; // 计算上一行dp的前缀和
        for (int k = 1; k <= m; k++)
            sum[k] = (sum[k - 1] + dp[i - 1][k]) % MOD;
        for (int j = 0; j <= m; j++) // 转移当前dp[i][j]
            dp[i][j] = getsum(max(0, j - a[i - 1]), j);
    }
    cout << dp[n][m] << endl;
    return 0;
}

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll MOD=1e9+7;
int n,m,a[105];
ll dp[105][100005],sum[100005];
ll getsum(int l,int r)//前缀和
{
	return (l==0?sum[r]:(sum[r]+MOD-sum[l-1])%MOD);
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)
		cin>>a[i];
	dp[0][0]=1ll;
	for(int i=1;i<=n;i++)
	{
		sum[0]=dp[i-1][0];//处理上一行dp的前缀和
			for(int k=1;k<=m;k++)
				sum[k]=(sum[k-1]+dp[i-1][k])%MOD;
		for(int j=0;j<=m;j++) //按公式转移
			dp[i][j]=getsum(max(0,j-a[i-1]),j);
	}
	cout<<dp[n][m]<<endl;
	return 0;
}