将递归调用结果存储在变量中会导致 DP 记忆解决方案中的计算不正确

Question

仅使用注释代码而不是在 max 函数内进行递归调用，会导致错误的结果，特别是在以下测试用例中

int main() {
    Solution obj = Solution();
    vector<string> arr {"0","11","1000","01","0","101","1","1","1","0","0","0","0","1","0",
                    "0110101","0","11","01","00","01111","0011","1","1000","0","11101",
                    "1","0","10","0111"};
    // output: 17
    cout << obj.findMaxForm(arr, 9, 80) << endl;
    return 0;
}

正确的输出是 17，但在这种情况下它给了我 14。 此外，如果您未注释 take 和 left 行，而仅注释 memoization 行，它将输出正确的结果

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int dfsHelper(vector<string>& strs, int idx, pair<int, int>& target, pair<int, int> curr, int result,
                                                                    vector<vector<vector<int>>>& memo) {
        if (curr.first > target.first || curr.second > target.second) return 0;
        if (idx >= strs.size()) return result;
        if (memo[idx][curr.first][curr.second] != -1) return memo[idx][curr.first][curr.second];

        pair<int, int> addition {0, 0};
        for (char& ch: strs[idx]){
            if (ch == '0') addition.first += 1;
            else addition.second += 1;
        }

//        int leave = dfsHelper(strs, idx+1, target, curr, result, memo);
//        int take = dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo);
//        memo[idx][curr.first][curr.second] = max(leave, take);
        memo[idx][curr.first][curr.second] = max(
                dfsHelper(strs, idx+1, target, curr, result, memo),
                dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo)
                );
        return memo[idx][curr.first][curr.second];
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        pair<int, int> target {m, n};
        vector<vector<vector<int>>> memo(strs.size(), vector<vector<int>>(m+1, vector<int>(n+1, -1)));
        return dfsHelper(strs, 0, target, {0, 0}, 0, memo);
    }
};

实际上我花了几个小时试图解决这里的问题，但这都是我设法找到的，我更倾向于记忆有一些问题的情况，但我无法弄清楚

Answer 1

这样做时得到不同结果的原因：

    int leave = dfsHelper(strs, idx+1, target, curr, result, memo);
    int take = dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo);
    memo[idx][curr.first][curr.second] = max(leave, take);

而不是这个：

    memo[idx][curr.first][curr.second] = max(
            dfsHelper(strs, idx+1, target, curr, result, memo),
            dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo)
            );

是在第二组代码中，您使用

std::max

的结果调用

dfsHelper

，但未指定 C++ 中参数的求值顺序。 因此很有可能

dfsHelper(strs, idx+1, target, {curr.first+addition.first, curr.second+addition.second}, result+1, memo)

之前评价过

dfsHelper(strs, idx+1, target, curr, result, memo)

但是，在分别计算

leave

和

take

的代码中，您始终在

leave

之前评估

take

。

如果颠倒

leave

和

take

的顺序，结果将是17：

int take = dfsHelper(strs, idx+1, target, {curr.first+addition.first,         
                     curr.second+addition.second}, result+1, memo);
int leave = dfsHelper(strs, idx+1, target, curr, result, memo);
memo[idx][curr.first][curr.second] = max(leave, take);

实例

因此，实际正确的代码是您不依赖于调用

std::max

中的求值顺序的代码。你只是“幸运”，

std::max

在第一个参数之前评估了第二个参数。