Recursive + Memoize


#1

Why this code is giving a TLE?
int dp[1001][1001];

int knapsack(vectorv , vector w , int c , int i , int wt)
{
if(dp[i][wt] != -1)
return dp[i][wt];

if(i>=v.size())
return dp[i][wt] = 0;

if(wt > c)
return dp[i][wt] = 0;

if(wt + w[i] <= c)
{
    int temp1 = v[i] + knapsack(v,w,c,i+1,wt+w[i]);
    int temp2 = knapsack(v,w,c,i+1,wt);

    return dp[i][wt] = max(temp1 , temp2);
}

else
    return dp[i][wt] = knapsack(v,w,c,i+1,wt);

}

int Solution::solve(vector &A, vector &B, int C) {

memset(dp , -1 , sizeof(dp));

return knapsack(A,B,C,0,0);

}


#2

replace int knapsack(vectorv , vector w , int c , int i , int wt) with int knapsack(vector &v , vector &w , int c , int i , int wt), i think it will work then. U are trying for call by value, but since u are using lot of space already after creating dp the size is exceeding, so if u try using & it wont add up any extra memory.


#3

yes u are right , it worked.
Thank you!