# 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.

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

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