Help CSES Dp problem TLE

Book shop dp problem top down dp approach giving tle

my code:

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;

const int mod=pow(10,9)+7;

int main()
{

int n,x;
int price[1001],pages[1001];
int dp[1005][100005];
memset(dp,0,sizeof(dp));
cin>>n>>x;
for(int i=0;i<n;i++)
{
cin>>price[i];
}
for(int i=0;i<n;i++)
{
cin>>pages[i];
}
for(ll i=0;i<=n;i++)
{
for(ll j=0;j<=x;j++)
{
if(i==0 || j==0)
{
dp[i][j]=0;
}
else
{
break;
}
}
}
for(ll i=1;i<=n;i++)
{
for(ll j=1;j<=x;j++)
{

    if(j-price[i-1]>=0)
    {
        dp[i][j]=max(dp[i-1][j-price[i-1]]+pages[i-1],dp[i-1][j]);
    }
    else
    {
        dp[i][j]=dp[i-1][j];
    }
}

}
cout<<dp[n][x];
return 0;
}

You’ll have to use iterative DP for this problem. I don’t think there is any other way to get around that Runtime Error “RecursionError: maximum recursion depth exceeded in comparison”.

Its similar to 0/1 knapsack problem. :grin:

It is the 0/1 Knapsack problem (in disguise :grin:).

1 Like
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int MOD=1e9+7;
#define _f .first
#define _s .second
int32_t main() {
    int n,x;
    cin>>n>>x;
    vector<pair<int,int>> books(n+1);
    for(int i=1;i<=n;i++){
        cin>>books[i]_f;
    }
    for(int i=1;i<=n;i++){
        cin>>books[i]_s;
    }    
    int dp[n+1][x+1];
    for(int i=0;i<=n;i++){
        for(int j=0;j<=x;j++){
            if(i==0||j==0)dp[i][j]=0;
            else if(books[i]_f <= j)
                dp[i][j] = max(books[i]_s+ dp[i-1][j-books[i]_f], dp[i-1][j]);
            else
                dp[i][j] = dp[i-1][j];
            //cout<<dp[i][j]<<" ";
        }
       // cout<<"\n";
    }
    cout<<dp[n][x];
    return 0;
}

That is it