urparvezali's blog

By urparvezali, history, 12 months ago, In English

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

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

By urparvezali, history, 21 month(s) ago, In English

If you need to determine minimum and maximum in C++ from a certain value or variable then you can try it

int maxNum = max({a,b,c});
int minNum = min({a,b,c});
or
int maxNum = max({n1,n2,n3,n4....nn});
int minNum = min({n1,n2,n3,n4....nn});

where a,b,c and n1,n2,n3...nn are variables or values

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it