Dp top-down [Help]
Difference between en1 and en2, changed 23 character(s)
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);↵
    ↵
}↵

//↵
~~~~~↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English 15411019 2019-08-16 14:53:10 23
en1 English 15411019 2019-08-16 14:51:41 1258 Initial revision (published)