c++ dp solution


  • 0
    H
    class Solution {
    public:
    	int findMaxForm(vector<string>& strs, int m, int n) {
    		int ns = strs.size();
    		if (ns == 0)
    			return 0;
    		int ans = 0;
    		vector<pair<int, int> > vp;
    		vector<vector<pair<int,int> > > dp(m+1);
    		for (int i = 0; i <= m; i++)
    			dp[i].resize(n + 1);
    		for (int i = 0; i < ns; i++) {
    			int ms = strs[i].size();
    			int sn = 0, sm = 0;
    			for (int j = 0; j < ms; j++) {
    				if (strs[i][j] == '0')
    					sm++;
    				else if (strs[i][j] == '1')
    					sn++;
    			}
    			vp.push_back(pair<int, int>(sm, sn));
    		}
    		if (vp[0].first <= m&&vp[0].second <= n) {
    			dp[vp[0].first][vp[0].second].first = 1;
    			dp[vp[0].first][vp[0].second].second = 0;
    			ans = 1;
    		}
    		for (int i = 1; i < ns; i++) {
    			int t = 0;
    			for (int j = 0; j <= m; j++) {
    				for (int k = 0; k <= n; k++) {
    					if (dp[j][k].first != 0&&dp[j][k].second!=i) {
    						if ((j + vp[i].first <= m&&k + vp[i].second <= n) && dp[j + vp[i].first][k + vp[i].second].first < dp[j][k].first + 1) {
    							dp[j + vp[i].first][k + vp[i].second].first = dp[j][k].first + 1;
    							dp[j + vp[i].first][k + vp[i].second].second = i;
    							if (dp[j][k].first + 1 > t) {
    								t = dp[j][k].first + 1;
    							}
    						}
    					}
    				}
    			}
    			if ((vp[i].first <= m&&vp[i].second <= n)&& dp[vp[i].first][vp[i].second].first < 1) {
    				dp[vp[i].first][vp[i].second].first = 1;
    				dp[vp[i].first][vp[i].second].second = i;
    				if (t < 1)
    					t = 1;
    			}
    			if (t > ans)
    				ans = t;
    		}
    		return ans;
    	}
    };
    

Log in to reply
 

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