Sometimes one number is not enough to describe a dynamic programming subproblem. Suppose we have processed several objects, but the future also depends on how much of some resource we have used. We must remember both facts.
This leads to a two-dimensional state such as dp[i][j]. Usually, one coordinate describes our progress and the other describes an important property of the processed part.
Problem or motivation
There are n children and k identical candies. Child i may receive any number of candies from 0 to .
ai
Count the number of valid distributions in which exactly k candies are given away. Since the answer may be large, calculate it modulo 109+7.
For example, let n=3, k=3, and a=[1,2,2]. The valid distributions (x1,x2,x3) are:
(0,1,2);
(0,2,1);
(1,0,2);
(1,1,1);
(1,2,0).
Therefore, the answer is 5.
Core concept
The two-dimensional state
Let dp[i][j] be the number of ways to distribute exactly j candies among the first i children while respecting their limits.
The two coordinates have separate jobs:
i tells us which prefix of children has already been processed;
j tells us the exact total number of candies given to that prefix.
Before processing any child, there is one way to distribute zero candies: do nothing. Therefore, dp[0][0]=1. It is impossible to give a positive number of candies to an empty prefix, so dp[0][j]=0 for every j>0.
Now consider child i and state dp[i][j]. Suppose this child receives x candies. The first i−1 children must then receive exactly j−x candies. The value of x may be anything from 0 to min(ai,j), so the transition is
dp[i][j]=x=0∑min(ai,j)dp[i−1][j−x]
This is the usual last-choice view of prefix DP: choose what happens to the last object of the prefix, then use an answer for the shorter prefix.
Every state in row i depends only on row i−1, so we process the children from 1 to n. The final answer is dp[n][k].
Exact and at-most states
The word “exactly” is part of the state definition. State dp[i][j] does not include distributions using fewer than j candies. This makes the transition precise and makes the required answer a single cell.
If the task asked for at most k candies, we could still use the same exact state and sum dp[n][0],…,dp[n][k] at the end. Silently changing the state to “at most j” would require a different transition and is a common source of mistakes.
Main algorithm
The direct transition tries every possible value of x for every pair (i,j). If A=maxai, its time complexity is O(nkA), which may become O(nk2).
Look at the values used for one state more carefully. They form one continuous segment of the previous row:
dp[i−1][j]+dp[i−1][j−1]+⋯+dp[i−1][max(0,j−ai)]
Whenever a transition asks for the sum of a continuous segment, prefix sums are a natural optimization. For the previous DP row, define pref[j]=∑s=0jdp[i−1][s].
The required segment starts at max(0,j−ai) and ends at j. Therefore, we begin with pref[j]. If j−ai−1≥0, we subtract pref[j−ai−1] to remove everything before the segment.
Thus, each state is calculated in O(1) after building the prefix sums of the previous row.
Algorithm:
Implementation
Complexity
Time:O(nk)
Memory:O(nk)
1. Set every dp state to 0.
2. Set dp[0][0] = 1.
3. For every child i from 1 to n:
3.1. Set pref[0] = dp[i - 1][0].
3.2. For every total j from 1 to k:
3.2.1. Set pref[j] = pref[j - 1] + dp[i - 1][j].
3.2.2. Take pref[j] modulo mod.
3.3. For every total j from 0 to k:
3.3.1. Set dp[i][j] = pref[j].
3.3.2. Set left = j - a[i].
3.3.3. If left > 0, subtract pref[left - 1] from dp[i][j].
3.3.4. Normalize dp[i][j] modulo mod.
4. Output dp[n][k].
#include <bits/stdc++.h>using namespace std;const int N = 1005;const int mod = 1e9 + 7;int a[N];int dp[N][N];int pref[N];int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; for(int i = 1; i <= n; i++){ cin >> a[i];} dp[0][0] = 1; for(int i = 1; i <= n; i++){ pref[0] = dp[i - 1][0]; for(int j = 1; j <= k; j++){ pref[j] = pref[j - 1] + dp[i - 1][j]; if(pref[j]>= mod){ pref[j] -= mod;}} for(int j = 0; j <= k; j++){ dp[i][j] = pref[j]; int left = j - a[i]; if(left > 0){ dp[i][j] -= pref[left - 1]; if(dp[i][j]< 0){ dp[i][j] += mod;}}}} cout << dp[n][k]<< endl; return 0;}