Сохранение результата рекурсивного вызова в переменной приводит к неверным расчетам в запоминаемом решении DP. ⇐ C++

[Anonymous]

Просто использование прокомментированного кода вместо рекурсивных вызовов внутри функции max приводит к некорректному результату, особенно в следующем тестовом примере

Код: Выделить всё

int main() {
Solution obj = Solution();
vector 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  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 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& strs, int m, int n) {
pair target {m, n};
vector memo(strs.size(), vector(m+1, vector(n+1, -1)));
return dfsHelper(strs, 0, target, {0, 0}, 0, memo);
}
};

на самом деле я потратил часы, пытаясь решить проблему здесь, но это все, что мне удалось найти, я больше склоняюсь к тому, что с мемоизацией есть некоторые проблемы, но я могу' не могу понять

Подробнее здесь: https://stackoverflow.com/questions/792 ... culation-i