How to reduce the number of states in DP?

I was solving the “Candies” problem in Atcoder Educational DP Contest. Even though I could solve the problem using two states (after a lot of WA’s initially :laughing: ) I was surprised to see some codes where the solution used only a one dimensional DP array, whereas I had used two 2D arrays, one to store the DP values and the other for the prefix sums. Now what I want to ask is that how do you go about reducing the number of states in your DP and then planning the DP transition accordingly?

Let us look at our initial dp. dp_{i,j} = \sum\limits_{l=j-a_i}^{j} dp_{i-1,l}
Where dp_{i,j} represents the number of ways to distribute j candies among the first i children.

To remove the prefix sum array, Let us define dp_{i,j} as the number of ways to distribute at least j candies among i children. This allows us to create an O(1) transition.

dp_{i,j} = dp_{i,j+1} + dp_{i-1,j-a_i} - dp_{i-1,j+1}.

Using this we can ignore the prefix sum array.

To remove the first dimension, we can notice we need to save only dp_i and dp_{i-1}.

This will still need 2\ \ 1D arrays. We can reduce it even further, by iterating j from k to 0, and then, using dp_j = dp_{j+1} + dp_{j-a_i} - //dp_{j+1}.

The problem is the last term. The last term is actually dp_{i,j+1}. To fix that, we will need a variable to remember r = dp_{i-1,j+1}.

So dp_j = dp_{j+1} + dp_{j-a_i} - r.

Code
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
const int p = 1e9 + 7;
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> seq(n);
    for(auto &x : seq){
        cin>>x;
    }
    vector<int> dp(k+2);
    dp[0] = 1;
    for(int i=0;i<n;i++){
        for(int j=k,l=0,r=0;j>=0;--j){
            l = r;
            r = dp[j];
            dp[j] = dp[j+1] + dp[max(0, j-seq[i])] - l;  
            dp[j] >=p ? dp[j]-=p : dp[j];
            dp[j] < 0 ? dp[j]+=p : dp[j]; 
        }
    }
    cout<<dp[k]<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

Also this doesn’t actually reduce the number of states, rather the maximum number of states you need to remember at at time.

3 Likes

Is there a way to do this with top down dp ?
I looked at a lot of submission, but it seems everyone did it with bottom up, maybe because it’s hard to do prefix sum with top down. But I am not sure.

Likely possible with O(1) transitions, but I’m not sure how to do it in O(k) space.
I don’t think that’s possible.