Bismillahir Rahmanir Rahim↵
While solving the CSES-[BOOK Shop](https://cses.fi/problemset/task/1158/) problem, I used TOP DOWN approach having complexity O(n.m) approach at first. But it gives TLE. But when I used bottom up approach, it got accepted.↵
Why my Top Down approach got TLE ?I am confused.↵
↵
TOP DOWN approach↵
==================↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#include<iostream>↵
#define ff first↵
#define ss second ↵
#define pb push_back↵
#define ll long long↵
#define noob ios::sync_with_stdio(0);cin.tie(0);↵
using namespace std;↵
int n;↵
int a[1005],b[1005],dp[1005][100005];↵
int solve(int i,int m){↵
if(i==n){↵
return 0;↵
}↵
if(dp[i][m]!=-1)return dp[i][m];↵
int ans=0;↵
ans=max(ans,solve(i+1,m));↵
if(m>=a[i]){↵
ans=max(ans,solve(i+1,m-a[i])+b[i]);↵
}↵
return dp[i][m]= ans;↵
}↵
int main(){↵
int m;↵
cin>>n>>m;↵
memset(dp,-1,sizeof(dp));↵
for(int i=0;i<n;i++)cin>>a[i];↵
for(int j=0;j<n;j++)cin>>b[j];↵
cout<<solve(0,m)<<endl;↵
return 0;↵
↵
↵
}↵
↵
~~~~~↵
↵
BOTTOM UP approach↵
==================↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#include<iostream>↵
#define ff first↵
#define ss second ↵
#define pb push_back↵
#define ll long long↵
#define noob ios::sync_with_stdio(0);cin.tie(0);↵
using namespace std ;↵
int main(){↵
int n,m;↵
cin>>n>>m;↵
vector<int>a(n),b(n);↵
for(int i=0;i<n;i++)cin>>a[i];↵
for(int j=0;j<n;j++)cin>>b[j];↵
int dp[n+1][m+1];↵
memset(dp,0,sizeof(dp));↵
for(int i=1;i<=n;i++){↵
for(int j=0;j<=m;j++){↵
dp[i][j]=dp[i-1][j];↵
if(j>=a[i-1]){↵
dp[i][j]=max(dp[i][j],dp[i-1][j-a[i-1]]+b[i-1]);↵
}↵
}↵
}↵
cout<<dp[n][m]<<endl;↵
}↵
~~~~~↵
↵
↵
↵
While solving the CSES-[BOOK Shop](https://cses.fi/problemset/task/1158/) problem, I used TOP DOWN approach having complexity O(n.m) approach at first. But it gives TLE. But when I used bottom up approach, it got accepted.↵
Why my Top Down approach got TLE ?I am confused.↵
↵
TOP DOWN approach↵
==================↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#include<iostream>↵
#define ff first↵
#define ss second ↵
#define pb push_back↵
#define ll long long↵
#define noob ios::sync_with_stdio(0);cin.tie(0);↵
using namespace std;↵
int n;↵
int a[1005],b[1005],dp[1005][100005];↵
int solve(int i,int m){↵
if(i==n){↵
return 0;↵
}↵
if(dp[i][m]!=-1)return dp[i][m];↵
int ans=0;↵
ans=max(ans,solve(i+1,m));↵
if(m>=a[i]){↵
ans=max(ans,solve(i+1,m-a[i])+b[i]);↵
}↵
return dp[i][m]= ans;↵
}↵
int main(){↵
int m;↵
cin>>n>>m;↵
memset(dp,-1,sizeof(dp));↵
for(int i=0;i<n;i++)cin>>a[i];↵
for(int j=0;j<n;j++)cin>>b[j];↵
cout<<solve(0,m)<<endl;↵
return 0;↵
↵
↵
}↵
↵
~~~~~↵
↵
BOTTOM UP approach↵
==================↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
#include<iostream>↵
#define ff first↵
#define ss second ↵
#define pb push_back↵
#define ll long long↵
#define noob ios::sync_with_stdio(0);cin.tie(0);↵
using namespace std ;↵
int main(){↵
int n,m;↵
cin>>n>>m;↵
vector<int>a(n),b(n);↵
for(int i=0;i<n;i++)cin>>a[i];↵
for(int j=0;j<n;j++)cin>>b[j];↵
int dp[n+1][m+1];↵
memset(dp,0,sizeof(dp));↵
for(int i=1;i<=n;i++){↵
for(int j=0;j<=m;j++){↵
dp[i][j]=dp[i-1][j];↵
if(j>=a[i-1]){↵
dp[i][j]=max(dp[i][j],dp[i-1][j-a[i-1]]+b[i-1]);↵
}↵
}↵
}↵
cout<<dp[n][m]<<endl;↵
}↵
~~~~~↵
↵
↵
↵
