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:

1. The given numbers of 0s and 1s will both not exceed 100
2. 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