问题描述
思路分析
求最值问题，并且需要考虑所有的情况，所以可以用动态规划来写。题中是要选出最大的子集，首先，明确状态，dp[i][j][k]表示考虑第strs[0]到strs[i]，0的个数为j，1的个数为k的最大子集。 对应每一个字符串，就有选还是不选的问题。所以状态方程是 dp[i][j][k]=max(dp[i-1][j][k]（不选）,dp[i-1][j-num0][k-num1]+1（选）); 然后还有一个步骤就是初始化的问题，那就是考虑第一个字符串对应的dp数组应该如何写，具体见代码
代码
class Solution {
public:
int findMaxForm(vector
<string
>& strs
, int m
, int n
) {
int len
=strs
.size();
int num0
=0,num1
=0;
vector
<vector
<vector
<int> > > dp(len
,vector
<vector
<int> > (m
+1,vector
<int>(n
+1,0) ));
for(int x
=0;x
<strs
[0].size();x
++) {
if(strs
[0][x
]=='0') num0
++;
else num1
++;
}
for(int i
=0;i
<=m
;i
++) {
for(int j
=0;j
<=n
;j
++) {
if(num0
<=i
&&num1
<=j
) dp
[0][i
][j
]=1;
}
}
for(int i
=1;i
<=len
-1;i
++) {
num0
=0;
num1
=0;
for(int x
=0;x
<strs
[i
].size();x
++) {
if(strs
[i
][x
]=='0') num0
++;
else num1
++;
}
for(int j
=0;j
<=m
;j
++) {
for(int k
=0;k
<=n
;k
++) {
dp
[i
][j
][k
]=dp
[i
-1][j
][k
];
if(j
>=num0
&&k
>=num1
)
dp
[i
][j
][k
]=max(dp
[i
][j
][k
],dp
[i
-1][j
-num0
][k
-num1
]+1);
}
}
}
return dp
[len
-1][m
][n
];
}
};
