记忆在这里有什么帮助

Question

我刚刚解决了子集和问题：

给定大小为N的整数数组nums。你还得到了一个整数B，你需要找到nums中是否存在一个子集，其和为B。如果存在子集，则返回1，否则返回0。

约束条件为：1 <= N <= 100；1 <= nums[i] <= 100；1 <= B <= 10^5；

我解决这个问题的方法如下(0/1背包(：

vector<int> n;
int t;
unordered_map<string, long long> m;
int helper(int i, int sum) {
if(i>=n.size()) return sum==t;
string str=to_string(i)+"-"+to_string(sum);
if(m.count(str)) return m[str];
int val=helper(i+1, sum+n[i]);
val=max(val, helper(i+1, sum));
return m[str]=val;
}
int Solution::solve(vector<int> &nums, int B) {
n=nums;
t=B;
m.clear();

return helper(0,0);
}

这得到了"；接受"；。但是，请注意，nums中的所有值都是正的；因此IMO总额只会保持不变/继续增加。i也在增加。因此，我们永远不会遇到以前存储在记忆表中的值。

但是，如果我删除了记忆，它会导致一些大型测试用例的错误答案。我错过了什么？任何递归调用都会遇到以前的状态吗？

Answer 1

您调用helper两次，第二次的sum比第一次低。因此，对CCD_ 15的稍后呼叫确实可以具有与先前呼叫相同的CCD_ 16。

@user3386109已经给出了一组具体的num来演示这一点。至于频率，请考虑nums = [1, 1, ..., 1]100次的情况。然后在没有记忆的情况下，您将呼叫helper(100, 50)100 choose 50 = 100,891,344,545,564,193,334,812,497,256次。超过1亿个电话。。需要一段时间。