如何在递归函数中只定义和初始化一次变量

Question

我正在努力解决GeeksforGeeks上的0/1背包问题，它需要我完成功能

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

现在我想用递归+记忆来实现这一点。但为此，我需要为每个测试用例定义并初始化一个DP矩阵。它看起来像这样。

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

现在我能想到的是全局定义矩阵，并在函数内部使用memset，但问题是memset会在每次递归调用时重置矩阵。有办法绕过它吗？还是我只需要做制表法？

Answer 1

避免全局变量。

拆分您的方法：

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