参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！

474.一和零

力扣题目链接

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

算法公开课

《代码随想录》算法视频公开课：装满这个背包最多用多少个物品？| LeetCode：474.一和零，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

如果对背包问题不都熟悉先看这两篇：

动态规划：关于01背包问题，你该了解这些！
动态规划：关于01背包问题，你该了解这些！（滚动数组）

这道题目，还是比较难的，也有点像程序员自己给自己出个脑筋急转弯，程序员何苦为难程序员呢。

来说题，本题不少同学会认为是多重背包，一些题解也是这么写的。

其实本题并不是多重背包，再来看一下这个图，捋清几种背包的关系

多重背包是每个物品，数量不同的情况。

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

理解成多重背包的同学主要是把m和n混淆为物品了，感觉这是不同数量的物品，所以以为是多重背包。

但本题其实是01背包问题！

只不过这个背包有两个维度，一个是m 一个是n，而不同长度的字符串就是不同大小的待装物品。

开始动规五部曲：

确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。

然后我们在遍历的过程中，取dp[i][j]的最大值。

所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

此时大家可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

dp数组如何初始化

在动态规划：关于01背包问题，你该了解这些！（滚动数组）中已经讲解了，01背包的dp数组初始化为0就可以。

因为物品价值不会是负数，初始为0，保证递推的时候dp[i][j]不会被初始值覆盖。

确定遍历顺序

在动态规划：关于01背包问题，你该了解这些！（滚动数组）中，我们讲到了01背包为什么一定是外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

那么本题也是，物品就是strs里的字符串，背包容量就是题目描述中的m和n。

代码如下：

for (string str : strs) { // 遍历物品
    int oneNum = 0, zeroNum = 0;
    for (char c : str) {
        if (c == '0') zeroNum++;
        else oneNum++;
    }
    for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
        for (int j = n; j >= oneNum; j--) {
            dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
    }
}

有同学可能想，那个遍历背包容量的两层for循环先后循序有没有什么讲究？

没讲究，都是物品重量的一个维度，先遍历哪个都行！

举例推导dp数组

以输入：["10","0001","111001","1","0"]，m = 3，n = 3为例

最后dp数组的状态如下所示：

以上动规五部曲分析完毕，C++代码如下：

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        for (string str : strs) { // 遍历物品
            int oneNum = 0, zeroNum = 0;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) { // 遍历背包容量且从后向前遍历！
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

时间复杂度: O(kmn)，k 为strs的长度
空间复杂度: O(mn)

总结

不少同学刷过这道题，可能没有总结这究竟是什么背包。

此时我们讲解了0-1背包的多种应用，

纯 0 - 1 背包是求给定背包容量装满背包的最大价值是多少。
416. 分割等和子集是求给定背包容量，能不能装满这个背包。
1049. 最后一块石头的重量 II 是求给定背包容量，尽可能装，最多能装多少
494. 目标和是求给定背包容量，装满背包有多少种方法。
本题是求给定背包容量，装满背包最多有多少个物品。

所以在代码随想录中所列举的题目，都是 0-1背包不同维度上的应用，大家可以细心体会！

其他语言版本

Java

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]表示i个0和j个1时的最大子集
        int[][] dp = new int[m + 1][n + 1];
        int oneNum, zeroNum;
        for (String str : strs) {
            oneNum = 0;
            zeroNum = 0;
            for (char ch : str.toCharArray()) {
                if (ch == '0') {
                    zeroNum++;
                } else {
                    oneNum++;
                }
            }
            //倒序遍历
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

Python

DP（版本一）

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # 创建二维动态规划数组，初始化为0
        for s in strs:  # 遍历物品
            zeroNum = s.count('0')  # 统计0的个数
            oneNum = len(s) - zeroNum  # 统计1的个数
            for i in range(m, zeroNum - 1, -1):  # 遍历背包容量且从后向前遍历
                for j in range(n, oneNum - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)  # 状态转移方程
        return dp[m][n]

DP（版本二）

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # 创建二维动态规划数组，初始化为0
        # 遍历物品
        for s in strs:
            ones = s.count('1')  # 统计字符串中1的个数
            zeros = s.count('0')  # 统计字符串中0的个数
            # 遍历背包容量且从后向前遍历
            for i in range(m, zeros - 1, -1):
                for j in range(n, ones - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)  # 状态转移方程
        return dp[m][n]

Go

func findMaxForm(strs []string, m int, n int) int {
	// 定义数组
	dp := make([][]int, m+1)
	for i,_ := range dp {
		dp[i] = make([]int, n+1 )
	}
	// 遍历
	for i:=0;i<len(strs);i++ {
		zeroNum,oneNum := 0 , 0
		//计算0,1 个数
		//或者直接strings.Count(strs[i],"0")
		for _,v := range strs[i] {
			if v == '0' {
				zeroNum++
			}
		}
		oneNum = len(strs[i])-zeroNum
		// 从后往前 遍历背包容量
		for j:= m ; j >= zeroNum;j-- {
			for k:=n ; k >= oneNum;k-- {
				// 推导公式
				dp[j][k] = max(dp[j][k],dp[j-zeroNum][k-oneNum]+1)
			}
		}
		//fmt.Println(dp)
	}
	return dp[m][n]
}

func max(a,b int) int {
	if a > b {
		return a
	}
	return b
}

Javascript

const findMaxForm = (strs, m, n) => {
    const dp = Array.from(Array(m+1), () => Array(n+1).fill(0));
    let numOfZeros, numOfOnes;

    for(let str of strs) {
        numOfZeros = 0;
        numOfOnes = 0;
    
        for(let c of str) {
            if (c === '0') {
                numOfZeros++;
            } else {
                numOfOnes++;
            }
        }

        for(let i = m; i >= numOfZeros; i--) {
            for(let j = n; j >= numOfOnes; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - numOfZeros][j - numOfOnes] + 1);
            }
        }
    }

    return dp[m][n];
};

TypeScript

滚动数组，二维数组法

type BinaryInfo = { numOfZero: number, numOfOne: number };
function findMaxForm(strs: string[], m: number, n: number): number {
    const goodsNum: number = strs.length;
    const dp: number[][] = new Array(m + 1).fill(0)
        .map(_ => new Array(n + 1).fill(0));
    for (let i = 0; i < goodsNum; i++) {
        const { numOfZero, numOfOne } = countBinary(strs[i]);
        for (let j = m; j >= numOfZero; j--) {
            for (let k = n; k >= numOfOne; k--) {
                dp[j][k] = Math.max(dp[j][k], dp[j - numOfZero][k - numOfOne] + 1);
            }
        }
    }
    return dp[m][n];
};
function countBinary(str: string): BinaryInfo {
    let numOfZero: number = 0,
        numOfOne: number = 0;
    for (let s of str) {
        if (s === '0') {
            numOfZero++;
        } else {
            numOfOne++;
        }
    }
    return { numOfZero, numOfOne };
}

传统背包，三维数组法

type BinaryInfo = { numOfZero: number, numOfOne: number };
function findMaxForm(strs: string[], m: number, n: number): number {
    /**
        dp[i][j][k]: 前i个物品中, 背包的0容量为j, 1容量为k, 最多能放的物品数量
     */
    const goodsNum: number = strs.length;
    const dp: number[][][] = new Array(goodsNum).fill(0)
        .map(_ => new Array(m + 1)
            .fill(0)
            .map(_ => new Array(n + 1).fill(0))
        );
    const { numOfZero, numOfOne } = countBinary(strs[0]);
    for (let i = numOfZero; i <= m; i++) {
        for (let j = numOfOne; j <= n; j++) {
            dp[0][i][j] = 1;
        }
    }
    for (let i = 1; i < goodsNum; i++) {
        const { numOfZero, numOfOne } = countBinary(strs[i]);
        for (let j = 0; j <= m; j++) {
            for (let k = 0; k <= n; k++) {
                if (j < numOfZero || k < numOfOne) {
                    dp[i][j][k] = dp[i - 1][j][k];
                } else {
                    dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - numOfZero][k - numOfOne] + 1);
                }
            }
        }
    }
    return dp[dp.length - 1][m][n];
};
function countBinary(str: string): BinaryInfo {
    let numOfZero: number = 0,
        numOfOne: number = 0;
    for (let s of str) {
        if (s === '0') {
            numOfZero++;
        } else {
            numOfOne++;
        }
    }
    return { numOfZero, numOfOne };
}

回溯法（会超时）

function findMaxForm(strs: string[], m: number, n: number): number {
    /**
        思路：暴力枚举strs的所有子集，记录符合条件子集的最大长度
     */
    let resMax: number = 0;
    backTrack(strs, m, n, 0, []);
    return resMax;
    function backTrack(
        strs: string[], m: number, n: number,
        startIndex: number, route: string[]
    ): void {
        if (startIndex === strs.length) return;
        for (let i = startIndex, length = strs.length; i < length; i++) {
            route.push(strs[i]);
            if (isValidSubSet(route, m, n)) {
                resMax = Math.max(resMax, route.length);
                backTrack(strs, m, n, i + 1, route);
            }
            route.pop();
        }
    }
};
function isValidSubSet(strs: string[], m: number, n: number): boolean {
    let zeroNum: number = 0,
        oneNum: number = 0;
    strs.forEach(str => {
        for (let s of str) {
            if (s === '0') {
                zeroNum++;
            } else {
                oneNum++;
            }
        }
    });
    return zeroNum <= m && oneNum <= n;
}

Scala

背包：

object Solution {
  def findMaxForm(strs: Array[String], m: Int, n: Int): Int = {
    var dp = Array.ofDim[Int](m + 1, n + 1)

    var (oneNum, zeroNum) = (0, 0)

    for (str <- strs) {
      oneNum = 0
      zeroNum = 0
      for (i <- str.indices) {
        if (str(i) == '0') zeroNum += 1
        else oneNum += 1
      }

      for (i <- m to zeroNum by -1) {
        for (j <- n to oneNum by -1) {
          dp(i)(j) = math.max(dp(i)(j), dp(i - zeroNum)(j - oneNum) + 1)
        }
      }
    }

    dp(m)(n)
  }
}

回溯法(超时)：

object Solution {
  import scala.collection.mutable

  var res = Int.MinValue

  def test(str: String): (Int, Int) = {
    var (zero, one) = (0, 0)
    for (i <- str.indices) {
      if (str(i) == '1') one += 1
      else zero += 1
    }
    (zero, one)
  }

  def travsel(strs: Array[String], path: mutable.ArrayBuffer[String], m: Int, n: Int, startIndex: Int): Unit = {
    if (startIndex > strs.length) {
      return
    }

    res = math.max(res, path.length)

    for (i <- startIndex until strs.length) {

      var (zero, one) = test(strs(i))

      // 如果0的个数小于m，1的个数小于n，则可以回溯
      if (zero <= m && one <= n) {
        path.append(strs(i))
        travsel(strs, path, m - zero, n - one, i + 1)
        path.remove(path.length - 1)
      }
    }
  }

  def findMaxForm(strs: Array[String], m: Int, n: Int): Int = {
    res = Int.MinValue
    var path = mutable.ArrayBuffer[String]()
    travsel(strs, path, m, n, 0)
    res
  }
}

Rust

impl Solution {
    pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
        let (m, n) = (m as usize, n as usize);
        let mut dp = vec![vec![0; n + 1]; m + 1];
        for s in strs {
            let (mut one_num, mut zero_num) = (0, 0);
            for c in s.chars() {
                match c {
                    '0' => zero_num += 1,
                    '1' => one_num += 1,
                    _ => (),
                }
            }
            for i in (zero_num..=m).rev() {
                for j in (one_num..=n).rev() {
                    dp[i][j] = dp[i][j].max(dp[i - zero_num][j - one_num] + 1);
                }
            }
        }
        dp[m][n]
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0474.一和零.md

0474.一和零.md

474.一和零

算法公开课

思路

总结

其他语言版本

Java

Python

Go

Javascript

TypeScript

Scala

Rust

Files

0474.一和零.md

Latest commit

History

0474.一和零.md

File metadata and controls

474.一和零

算法公开课

思路

总结

其他语言版本

Java

Python

Go

Javascript

TypeScript

Scala

Rust