Whenever I try to solve any dp problem it pushes my mind in the way of recursion. I cant think of looping dp but recursion. CSES DP Section problem BOOK SHOP, I tried to solve this but it got TLE 7/15 test cases after using dp vector of vector. how to solve this. As i cant think solving dp problem with iterative method please help me solving it recursively. this is my code below,

```
#include <bits/stdc++.h>
using namespace std;
int rec(int x, vector<pair<int, int>>& v, vector<vector<int>>& dp, int i, int n) {
if (i > n - 1) return 0;
if (dp[i][x] != -1) return dp[i][x];
int a = rec(x, v, dp, i + 1, n);
int b = 0;
if (x - v[i].first >= 0)
b = v[i].second + rec(x - v[i].first, v, dp, i + 1, n);
return dp[i][x] = max(a, b);
}
int main() {
int n, x;
cin >> n >> x;
vector<pair<int, int>> v(n);
for (auto& [i, j] : v) cin >> i;
for (auto& [i, j] : v) cin >> j;
vector<vector<int>> dp(n + 1, vector<int>(x + 1, -1));
cout << rec(x, v, dp, 0, n) << endl;
}
```

The key to solving DP problems like BOOK SHOP iteratively is to fill up the dp array in a bottom-up fashion instead of using recursive calls.

The iterative approach would be:

Initialize a 2D dp array of size n+1 x x+1. dp[i][j] will represent the max profit with the first i books and a budget of j. Fill up the dp array row-by-row iteratively:

for (int i = 1; i <= n; i++) { for (int j = 0; j <= x; j++) {

} }

The final answer is in dp[n][x]. This avoids recursion by calculating values in the dp table sequentially. It allows us to pass test cases in O(nx) memory.

Of course, it requires a bit of shift in thinking compared to a recursive approach. But with practice, iterative starts becoming more intuitive for DP problems.

This is a case of the classical problem called 0-1 knapsack.

dp[i][x] = maximum number of pages we can get for price at most x, only buying among the first i books.

Initially dp[0][x] = 0 for all x, as we can't get any pages without any books.

When calculating dp[i][x], we look at the last considered book, the i'th book. We either didn't buy it, leaving x money for the first i-1 books, giving dp[i-1][x] pages. Or we bought it, leaving x-price[i-1] money for the other i-1 books, and giving pages[i-1] extra pages from the bought book. Thus, buying the i'th book gives dp[i-1][x-price[i-1]] + pages[i-1] pages.

The complexity is O(n⋅x)

CODE:

vector<vector> dp(n + 1, vector(x + 1, 0)); for (int i = 1; i <= n; i++) {

Space optimized dp solution