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);

}

// ~~~~~

I am trying to solve this problem from Educational DP contest(atcoder) and having some issues with my code. Its working for all small test cases I can think of but when I submit I am getting runtime error. If anyone can tell what I am doing wrong, I am beginner.

Code:

#include <bits/stdc++.h>
using namespace std;

int n;
double prob[3001];
double dp[3001][3001];
bool vis[3001][3001];

double f(int c, int h){
    if(c==0 and h==0) return 1.0;
    if(c<0) return 0.0;
    
    if(vis[c][h]) return dp[c][h];
    
    dp[c][h] = (double)prob[c]*f(c-1,h-1)+(double)(1-prob[c])*f(c-1,h);
    vis[c][h] = true;
    
    return dp[c][h];
}


int main(){
    memset(dp,-1,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>prob[i];
    }
    double ans = 0.0;
    for(int i=n/2+1;i<=n;i++){
        ans = ans + f(n,i); 
    }
    
    cout<< fixed <<setprecision(20)<<ans;
}

Hey Guys,

I am trying to solve this problem [contest:260][problem:A](https://codeforces.net/contest/455/problem/A) tagged DP. I am getting runtime error for my submission in case of larger inputs.

n =int(input())
arr = [int(x) for x in input().split()]

freq = [0]*(n + 1)

for i in arr:
    freq[i] = freq[i] + 1

dic = {}
def dp(a):
    if a in dic:
        return dic[a]
    if(a==0):
        return 0
    if(a==1):
        return freq[1]
    res = max(dp(a-1), dp(a-2)+a*freq[a])
    dic[a] = res
    return res

print(dp(n))

Can anyone please explain what I am doing wrong, I am a beginner. Any help will be appreciated.