I_am_Vengeance's blog

Recursive DP — Prefix Sums
By I_am_Vengeance, history, 3 years ago, In English

Can anyone please explain how this problem can be solved in top-down manner (Recursive dp).

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Check the following implementation for small values of $$$K$$$ and $$$a_i$$$.

Recurive dp solution
→ Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Let dp[i][j] represent how many ways possible to distribute exactly j candies among first i participants. so dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2]........+dp[i-1][j-a[i]].

Calculating this sum if you are using loop will lead to O(n*k*k)

So you prefix sum instead . This prefix sum can be the dp array itself or another 2d array

Implementataion:

Using dp as prefix array only:

here and below is the main part

 for(int i=1;i<n;i++){
      for(int k=0;k<100001;k++){
          ll first=dp[i-1][k];
          ll second=((k-a[i]-1<0)?0:dp[i-1][k-a[i]-1]);
          dp[i][k]=(first-second+mod)%mod;
          dp[i][k]+=((k-1<0)?0:dp[i][k-1]);
          dp[i][k]%=mod;
      }
  }

using another 2d array to store prefix sums: here

→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

let $$$dp[i][j]$$$ = the number of ways to share $$$j$$$ candies among the remaining kids. We can write a $$$O(K * K * N)$$$ DP:

Code 1

However, this is too slow and will result in TLE. To optimize this, let's calculate all possible states starting from the $$$(i + 1)$$$-th kid before calculating any state starting from the $$$i$$$-th kid. We can see that $$$dp[i][j]$$$ = ($$$dp[i + 1][j]$$$ + $$$dp[i + 1][j - 1]$$$ + ... + $$$dp[i + 1][j - limit]$$$), limit is $$$min(j, a[i])$$$. If we store the prefix sum of states starting from the $$$(i + 1)$$$-th kid, we can compute the DP transition in $$$O(1)$$$ and reduce the complexity to $$$O(K * N)$$$.

Final code

Submission: Link

→ Reply