How to define and initialize a variable only once in a recursive function?

Question

I am trying to solve the 0/1 Knapsack problem on GeeksforGeeks and it requires me to complete the funtion

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

Now I want to do this with recursion + memoization. But to that I need to define and initialise a DP matrix for every test case. It looks like this.

int dp[1001][1001];
memset(dp,-1,sizeof(dp));

Now What I can think of is define the matrix globally and using memset inside function, but the problem arises is that memset would reset the matrix on every recursive call. Is there a way to get around it? or do I just have to do the tabulation method instead?

Why do you use `1001`? And what do you think `memset` with `-1` does? I would suggest reading a [good book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) instead of this utterly unprofessional website. — Evg, Dec 12 '20 at 08:23
memset initializes the matrix with -1 and i use 1001 because of the constraints — Parth Sharma, Dec 12 '20 at 08:46
Sorry, but this approach is broken in so many ways that it would require a pretty long answer to explain how a good solution might look like. Doing this in GeeksForGeeksish style is just a waste of time. All those `(int W, int wt[])`, `dp[1001][1001]`, and `memset` that they teach has nothing to do with professional C++ programming. Don't pick bad habit from the beginning and don't waste your time on Geeks. — Evg, Dec 12 '20 at 09:01
What would you suggest then @Evg ? the main issue i face with books is I cannot understand the language of books. It takes me half an hour to completely understand a page from the book. If you know a book in a very easy language, could you suggest? — Parth Sharma, Dec 12 '20 at 09:04
There is no universal answer. Try to find resources prepared by professional programmers. You can find a good book list at SO (link in the first comment). Another good list can be found [here](https://members.accu.org/index.php/book_reviews_redirect). Books for beginners are very readable. For example: C++ Primer by S.Lippman et al. — Evg, Dec 12 '20 at 09:16

score 0 · Accepted Answer · answered Dec 12 '20 at 09:10

Avoid global variable.

Split your method:

int knapSackRec(int (&dp)[1001][1001], int W, int wt[], int val[], int n)
{
    // ...
}

int knapSack(int W, int wt[], int val[], int n)
{
    int dp[1001][1001];
    memset(dp, -1, sizeof (dp));
    return knapSackRec(dp, W, wt, val, n);
}

How to define and initialize a variable only once in a recursive function?

1 Answers1