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

Question

我正在尝试解决 GeeksforGeeks 上的 0/1 Knapsack 问题，它需要我完成该功能

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