bash.ketchum's blog

Recursive DP does not pass in CSES?
By bash.ketchum, history, 2 years ago, In English

I've been trying to solve the DP section of CSES problemset and I noticed that usually the problems give TLE verdict if we're solving the problems using recursive DP. Am I doing something wrong, or the time limit is actually really strict?

Here is my solution for the problem Book Shop. Is there any way I can make my recursive solution faster?

Spoiler
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

HINT :

Relate it with Knapsack(classical) and you are good to go.

Recursive DP works with memoization (that too if time complexity is permitted).

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have actually solved it with Knapsack, but the problem is even with memoization the recursive solution is too slow (gets TLE on 2 of the testcases), but iterative solution works fine.

    int memo[1001][100001];
int value[1001];
int weight[1001];
int n,C;

int dp(int id, int remW){
    if((id==n) || remW==0) return 0;
    if(memo[id][remW] != -1){
        return memo[id][remW];
    }
    if(remW < weight[id]){
        return memo[id][remW] = dp(id+1, remW); //moved on
    }
    return memo[id][remW] = max(dp(id+1, remW), value[id]+dp(id+1, remW - weight[id]));
}

void solve(int kes){
    //write solution here
    cin>>n>>C;
    FOR(i, 0, n) cin>>weight[i];
    FOR(i, 0, n) cin>>value[i];
    memset(memo, -1, sizeof memo);
    printf("%d\n", dp(0, C));
}
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      Instead of using m x n 2D array use 2 x n array

      REFER THIS FROM Gfg =>https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/

      int knapSack(int W, int wt[], int val[], int n) {

      int i, w;
int K[2][W + 1];

for (i = 0; i <= n; i++) {
    for (w = 0; w <= W; w++) {
       if (i == 0 || w == 0)
         K[i % 2][w] = 0;
       else if (wt[i - 1] <= w)
         K[i % 2][w] = max(
          val[i - 1]
              + K[(i - 1) % 2][w - wt[i - 1]],
          K[(i - 1) % 2][w]);
       else
         K[i % 2][w] = K[(i - 1) % 2][w];
    }
}
return K[n % 2][W];

      }

      // Driver Code int main() { int val[] = { 60, 100, 120 }; int wt[] = { 10, 20, 30 }; int W = 50; int n = sizeof(val) / sizeof(val[0]);

      cout << knapSack(W, wt, val, n);

return 0;

      }

      → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      THe space u r taking is of order of 10^8 which is indeed the reason for time complexity .Try using 2 x n 2D array instead

      Refer to my code for more clarification Link: https://cses.fi/paste/2af885b03126b6a436292e/

      → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Well, the constraints are a bit tight, but recursion in itself slower than iteration in case of CPP Refer here

→ Reply