LeetCode 474 Ones and Zeroes
题目描述
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s
and n 1s
respectively. On the other hand, there is an array with strings consisting of only 0s
and 1s
.
Now your task is to find the maximum number of strings that you can form with given m 0s
and n 1s
. Each 0
and 1
can be used at most once.
Note:
- The given numbers of
0s
and1s
will both not exceed100
- The size of given string array won’t exceed
600
.
Example 1:
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3 Output: 4 Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
Example 2:
Input: Array = {"10", "0", "1"}, m = 1, n = 1 Output: 2 Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
一句话题意
给定一组只包含0和1的字符串,以及m个0、n个1。求用提供的m
个0和n
个1最多能拼成多少个给定字符串组中的字符串。
解题思路
背包问题,背包型动态规划的变种。
用dp[i][j][k]表示前i个字符串在0个数不超过j、1个数不超过k时最多能选取的字符串个数。统计第i个字符串中0和1个数分别为cnt_0[i]和cnt_1[i]。
如果取第i个字符串则 dp[i][j][k] = dp[i-1][j-cnt_0[i]][k-cnt_1[i]] + 1
如果不取第i个字符串则dp[i][j][k] = dp[i-1][j][k]
状态转移方程为:
dp[i][j][k]=max(dp[i-1][j-cnt_0[i]][k-cnt_1[i]] + 1 , dp[i-1][j][k])
由于dp[i][j][k]只与dp[i-1][*][*]相关,所以这里可以重复使用m*n的数组,将空间复杂度降为O(m*n),只需在遍历时从后向前遍历即可。
最终状态转移方程为
dp[j][k]=max(dp[j-cnt_0[i]][k-cnt_1[i]] + 1 , dp[j][k]) , 0<i<=l
0 条评论