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);
}
// ~~~~~