### urparvezali's blog

By urparvezali, history, 10 months ago,

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;
}

• +1

 » 10 months ago, # |   +1 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++) { // Don't take this book dp[i][j] = dp[i-1][j]; // Take this book if possible if (j >= v[i].first) { dp[i][j] = max(dp[i][j], dp[i-1][j - v[i].first] + v[i].second); }} }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.
•  » » 10 months ago, # ^ |   +1 for (int i = 1; i <= n; i++) { for (int j = 0; j <= x; j++) { // Don't take this book dp[i][j] = dp[i-1][j]; // Take this book if possible if (j >= v[i].first) { dp[i][j] = max(dp[i][j], dp[i-1][j - v[i].first] + v[i].second); } } } 
 » 10 months ago, # | ← Rev. 3 →   0 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 dp(n + 1, vector(x + 1, 0)); for (int i = 1; i <= n; i++) { for (int j = 0; j <= x; j++) { dp[i][j] = dp[i-1][j]; int left = j -price[i-1]; if (left >= 0) { dp[i][j] = max(dp[i][j], dp[i-1][left] + pages[i-1]); }}} cout << dp[n][x] <
 » 5 weeks ago, # |   0 import sys n, x = map(int, input().split()) prices = list(map(int, input().split())) pages = list(map(int, input().split())) dp = [0] * (x + 1) for i in range(n): price = prices[i] page = pages[i] for j in range(x, price - 1, -1): dp[j] = max(dp[j], dp[j - price] + page) print(dp[x]) `Space optimized dp solution