c++ recursion with memoization


  • 0
    H
    #include<bits/stdc++.h>
    using namespace std;
    
    int dp[107][107][601];
    
    class Solution {
        public:
            int findMaxForm(vector<string>& strs, int m, int n) {
                memset(dp,-1,sizeof dp);
                return f(strs,m,n,strs.size()-1);
            }
    
            int countZeroes(string s) {
                int cnt=0;
                for(int i=0;i<s.size();i++) {
                    if(s[i]=='0')
                        cnt++;
                }
                return cnt;
            }
    
            int f(vector<string>& strs, int m, int n,int index) {
                if(m < 0 || n < 0)
                    return -INT_MAX;
                if(index < 0)
                    return 0;
                if(dp[m][n][index] != -1)
                    return dp[m][n][index];
                int zeroes = countZeroes(strs[index]);
                int ones = strs[index].size() - zeroes;
                return dp[m][n][index] = max(f(strs,m,n,index-1), f(strs,m-zeroes,n-ones,index-1) + 1) ;
            }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.