Hello everybody,↵
I am trying to solve [this](https://atcoder.jp/contests/dp/tasks/dp_m)(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);↵
↵
}↵
↵
//↵
~~~~~↵
I am trying to solve [this](https://atcoder.jp/contests/dp/tasks/dp_m)(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
~~~~~↵
//↵
↵
#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);↵
↵
}↵
↵
//↵
~~~~~↵
