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
main, just like this.max. The order of evaluation of the arguments is not specified in C++. Maybe your code that outputs17just so happens to call the seconddfsHelperbefore the firstdfsHelper.