# c++ dp solution

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

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