我如何正确记忆这种复发关系？

Question

我正在解决一个问题：

给定整数列表nums，编写一个返回最大非贴上数字总和的函数。数字可以为0或负面。对于nums = [5，1，1，5]，输出应为10。

我已经实现的动态编程逻辑如下：

vector<pair<int,int>> dp;

int helper(vector<int>& nums, int i, bool include) {
    if(i>=nums.size()) return 0;
    pair<int,int> p=dp[i];
    if(p.first!=INT_MIN) return p.second;
    
    int maxval=0;
    if(include) maxval=nums[i]+helper(nums,i+1,false);
    maxval=max(maxval,helper(nums,i+1,true));

    dp[i]=make_pair(include,maxval);
    return maxval;
}

int solve(vector<int>& nums) {
    dp.clear();
    dp.resize(nums.size(),make_pair(INT_MIN,INT_MIN));

    // For all -ve numbers in input, just return `0`, as required.
    int ans=max({helper(nums,0,true),helper(nums,0,false),0});

    //for(auto& p: dp) {
    //    cout<<p.first<<" "<<p.second<<"\n";
    //}

    return ans;
}

当我不进行任何记忆时，我会得到正确的答案（所以我认为我的复发关系是正确的）；但是，在像上述记忆时，我得了错误的答案。

我正在用于记忆的逻辑：对于i th值，请在dp [i中存储a pair＆lt＆lt＆lt＆lt＆gt; ]，其中对的第一个值代表布尔值includ，而对的第二个值表示结果maxvalue针对i的当前值计算和包括。请注意，我对bool使用int，因为我需要三个值：true，false and“不尚未计算”。

我的回忆步骤中缺少什么？有什么更好的方法可以记住它吗？

谢谢。

Answer 1

不要过度思考。记忆函数f（p）{...返回expr; }，其中p是参数的元组，总是相同的。添加来自元组P的外部（不是递归函数的局部）映射m以返回值。然后重写f，因为

f(P) {
  if M contains key P, return M[P];
  ...
  t = Expr;
  M[P] = t;
  return t;
}

在您的函数中看起来，nums永远不会更改。因此，您可以从P中省略P。密钥元组具有类型＆lt; int，bool＆gt;，并且地图返回int。那就是map＆lt; tuple＆lt; int，bool＆gt;，int＆gt;。

如果映射键最终是一个自然数字，并且可能的范围很小，则可以用初始化的阵列替换备忘录图，该数组以某种值表示“无值”。然后，“包含密钥”测试将成为一个检查m [p]是否与“无值”不同的东西。在实际问题中，这并不经常发生。

我会让您算出其余的，因为看来您正在学习。注意是，在适当的实现中，您不会使地图成为全局变量。您将递归方法包装在类中，并制作nums和备忘录两个字段，因此不需要将它们作为参数传递。

Answer 2

int solve(const vector<int>& nums) {
    int N = nums.size();

    vector<int> dp(N, INT_MIN);
    function<int(int)> iter = [&](int i) {
        if(i>=N) { return 0; }
        if(dp[i] != INT_MIN) { return dp[i]; }
        return dp[i] = max(nums[i]+iter(i+2), iter(i+1));
    };
    
    return iter(0);
}

Answer 3

扫描阵列，记录三个最大数字及其位置。如果较大的两个不相邻，则它们的总和就是答案。如果较大的两个相邻，则（＃1 +＃3）或（＃2 +＃3）将是答案，具体取决于更大的。