Hello everybody, I am trying to solve this(M-Candies) problem from atcoder educational dp contest. I can think of a way to solve this in O(n*k^2) using dp(recursively) but it gets TLE. Now after looking at others solution I got the idea that we should maintain prefix sums and then calculate the number of ways(using bottom up approach). But I am trying to implement this using recursion, can anyone tell how can I maintain the prefix sum while solving this recursively. Any help will be appreciated.

Code(complexity — O(n*k^2)): ~~~~~

include <bits/stdc++.h>

using namespace std;

int dp[105][100007]; //ways- number of ways to distribute k candies among 1-n children int ways(int n,int k, int arr[]){ if(k<0) return 0; if(n==0 and k==0) return 1; if(n==0 and k!=0) return 0;

int &ans = dp[n][k];
if(ans!=-1) return ans;

ans = 0;
for(int i=0;i<=arr[n];i++){
    ans = ans + ways(n-1,k-i, arr);
}
return ans;

}

int main(){ memset(dp,-1,sizeof(dp)); int n, k; cin>>n>>k; int arr[n+1];

arr[0]=-1;
for(int i=1;i<=n;i++) cin>>arr[i];
cout<<ways(n,k,arr);

} ~~~~~