刷题刷到这里,先说题目:给定一组字符串,其中每个字符串中只包含‘0’和‘1’,给定你m个0 和n 个1,求最多能排出多少个字符串。
乍一看这题,貌似在哪里见过,貌似又没见过,哎,一排脑袋,01背包,只不过变成了二维的。在此,我们就先复习一下一维的01背包问题,以备后用~~~
N个物品,每个价值value[i], 需要占用空间need[i],给定一个登山包(不知道哪年买的。。。),容量为M,求用该登山包装这N个物品,最大价值能装多少。
不多说,直接dp,递推公式为dp[i][j] = max(dp[i-1][j], dp[i-1][j-need[i]]+value[i]),第一版代码如下:
点击(此处)折叠或打开
- for( i = 1; i <=N ; ++i)
- {
- for( j = 0; j <= M; j++)
- {
- if( j >= need[i] )
- best[i][j] = max( best[i-1][j], best[i-1][j - need[i]] + value[i]);
- else
- best[i][j] = best[i-1][j];
- }
- }
接下来考虑优化问题,这种递推能不能将空间复杂度降低至O(M)呢,答案是肯定的,请看下面的代码:
点击(此处)折叠或打开
- for( i = 1; i <=N ; ++i)
- {
- for( j = M; j >= 0; --j)
- {
- if( j >= need[i] )
- best[j] = max( best[j], best[j - need[i]] + value[i]);
- }
- }
为什么对j要进行倒序遍历呢?这是因为在计算本轮第i个物品的时候,需要用到上一轮i-1个物品时的状态,而如果正向递增遍历,则会更新掉前面的数据,故采用倒叙遍历啦~~
有了如上的思路,变换为leetcode的题目,大家就不难找出解决思路了吧,先求出每个字符串对应需要的0和1的个数,相当于01背包中的need[i],给定的m和n相当于01背包中的背包容量M,代码如下:
点击(此处)折叠或打开
- int findMaxForm(vector<string>& strs, int m, int n){
- int len = strs.size(), i, j, M, N;
- if(len == 0||(m==0&&n==0)) return 0;
- vector<vector<int>> dp(len, vector<int>(2, 0));
- for(i = 0; i < len; i++)
- for(j = 0; j < strs[i].length(); j++){
- if(strs[i][j]=='0') dp[i][0]+=1;
- else dp[i][1]+=1;
- }
- vector<vector<int>> res(m+1, vector<int>(n+1, 0));
- for(i = 0; i < len; i++){
- for(M=m; M>=0;M--)
- for(N=n; N>=0;N--)
- if(M>=dp[i][0]&&N>=dp[i][1]){
- res[M][N]= max(res[M][N], res[M-dp[i][0]][N-dp[i][1]]+1);
- }
- }
- return res[m][n];
- }