Hi, I was solving problem Book Shop on CSES and found something interesting.
I tried this problem using two different ways:
First: Passed.
dp[i][j] : means maximum pages we can have if we are at shop number i and we have spent j amount of money;
The code is here :
void solve(){
ll n, m;
cin >> n >> m ;
vector<ll> prices(n+1), pages(n+1);
for(int i = 0 ; i < n ; i ++ ){
cin >> prices[i];
}
for(int i = 0 ; i < n; i ++ ){
cin >> pages[i];
}
vector<vector<int>> dp(n+1, vector<int> (m+1, 0));
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 0 ; j <= m ; j ++){
dp[i][j] = dp[i-1][j];
if(j - prices[i-1] >= 0){
dp[i][j] = max(dp[i][j], dp[i-1][j-prices[i-1]] + pages[i-1]);
}
}
}
cout << dp[n][m] << '\n';
}
Here the time compexity is n*m. The outer loop is running n times while the inner one is running m times, and it passed.
Second : TLE
dp[i][j] : maximum pages if we have used i amount of money and currently we are at j'th shop. The code :
void solve(){
ll n, m;
cin >> n >> m ;
vector<int> prices(n+1), pages(n+1);
for(int i = 0 ; i < n ; i ++ ){
cin >> prices[i];
}
for(int i = 0 ; i < n; i ++ ){
cin >> pages[i];
}
vector<vector<int>> dp(m+1, vector<int> (n+1, 0));
for(int i = 1 ; i <= m ; i ++ ){
for(int j = 1 ; j <= n ; j ++){
dp[i][j] = dp[i][j-1];
if(i - prices[j-1] >= 0){
dp[i][j] = max(dp[i][j], dp[i-prices[j-1]][j-1] + pages[j-1]);
}
}
}
cout << dp[m][n] << '\n';
}
Here also the time complexity is m*n. The outer loop is running m times while the inner one is running n times.
Since both have the same time complexity so why one of them is giving TLE ? Is there something that I am missing ?
