经典 'Subset Sum' 问题的这段代码有什么问题？

Question

问题陈述：给定一个整数列表 (nums) 和一个整数 x，检查列表中的某些（可能是所有）元素在添加时是否给出 x。

解决方案：

int dp[20001];
int recurse(vector<int>& nums, int x, int i) {
        
    if (x == 0)
        return 1;
        
    if (i < 0 or x < 0)
        return 0;
        
    if (dp[x] != -1)
        return dp[x];
        
    return dp[x] = recurse(nums, x - nums[i], i - 1) or recurse(nums, x, i - 1);
}
bool canPartition(vector<int>& nums, int x) {
        
    memset(dp, -1, sizeof dp);
    return recurse(nums, x, nums.size() - 1);
}

最后一行有问题。如果我改变递归的顺序，即先递归 (nums, x, i - 1) 然后递归 (nums, x - nums[i], i - 1)，我会得到错误的结果。例如，[1, 2, 3, 4, 5, 6, 7] -> False

我猜这与将明显错误的值放入 dp 数组有关，然后 returns 再次查找时相同。但请进一步说明。看不清楚。

PS: dp数组所有元素初始都是-1。

Answer 1

您的 dp 数组仅取决于 x 的值。但它应该取决于 x 和 i.

举个例子：

假设 nums = [1, 2, 3, 13] 且 x=13。

那么 recurse(nums, 13, 3) 应该 return 1，但是 recurse(nums, 13, 2) 应该 return 0。使用你的代码，如果你先调用 recurse(nums, 13, 2) 然后 dp[13] 将被分配一个不正确的结果。如果您有两个单独的条目 dp[13][3] 和 dp[13][2] 那么就不会有问题。

经典 'Subset Sum' 问题的这段代码有什么问题？

What is wrong with this code for the classic 'Subset Sum' problem?

c++

algorithm

dynamic-programming