Storing the recursive call result in a variable leads to incorrect calculation in a DP memoized solution

Just by using the commented code instead of making the recursive calls inside the max function, leads to incorrect result particularly with the following test case

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;
}

correct output is 17, but it gives me 14 in that case. Also if you left the take and leave lines uncommentd and just comment the lines of memoization it would output the correct results

#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);
    }
};

actually I have spent hours trying to get the problem here, but this all what I managed to find, I am more leaning to the case that the memoization has some issues, but I can't figure it out

The reason why you get different results when you do this:

    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);

instead of this:

    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)
            );

is that in the second set of code, you are calling std::max using the results of dfsHelper, but the order of evaluation of arguments in C++ is not specified. Thus it is more than likely that

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

was evaluated before

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

However, in the code where you are computing leave and take separately, you are always evaluation leave before take.

If you reverse the order of leave and take evaluations, the results will be 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);

Live Example

So the actual correct code is the one where you are computing leave/take separately, where take is computed before leave.

The code that calls std::max with two calls to dfsHelper, depending on compiler and compiler settings, may or may not work, thus cannot be relied on to give the correct results.

You were just fortunate that std::max(dfsHelper(...), dfsHelper(...)) evaluated the second argument before the first argument.