一和零

Tips

题目类型: Dynamic Programming

背包问题汇总

题目

给你一个二进制字符串数组 strs 和两个整数 m 和 n. 请你找出并返回 strs 的最大子集的长度, 该子集中最多有 m 个 0 和 n 个 1. 如果 x 的所有元素也是 y 的元素, 集合 x 是集合 y 的子集.

提示:

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

示例

输入: 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.

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

题解

典型的 0-1 背包 问题, 由于要往 m 和 n 两个背包放, 所以要写成三维 dp, 当然可以降到二维 dp.

JavaScript - 三维数组

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
  const len = strs.length

  // 先计算 strs 每个元素中 0 和 1 的个数
  const values = []
  for (const str of strs) {
    const tuple = [0, 0]
    for (const ch of str) {
      tuple[Number(ch)] += 1
    }
    values.push(tuple)
  }

  // 创建三维数组
  const dp = new Array(len + 1)
    .fill(0)
    .map(() => new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)))

  // 基本的 0-1 背包套路
  for (let i = 1; i <= len; i++) {
    const [zero, one] = values[i - 1]
    for (let j = 0; j <= m; j++) {
      for (let k = 0; k <= n; k++) {
        if (j - zero < 0 || k - one < 0) {
          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 - zero][k - one] + 1,
          )
        }
      }
    }
  }

  return dp[len][m][n]
}

JavaScript - 二维数组

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var findMaxForm = function (strs, m, n) {
  const len = strs.length

  const values = []
  for (const str of strs) {
    const tuple = [0, 0]
    for (const ch of str.split('')) {
      tuple[Number(ch)] += 1
    }
    values.push(tuple)
  }

  const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0))
  for (let i = 1; i <= len; i++) {
    const [zero, one] = values[i - 1]
    for (let j = m; j >= zero; j--) {
      for (let k = n; k >= one; k--) {
        dp[j][k] = Math.max(dp[j][k], dp[j - zero][k - one] + 1)
      }
    }
  }

  return dp[m][n]
}

Rust

use std::cmp;

pub fn find_max_form(strs: Vec<String>, m: i32, n: i32) -> i32 {
    let len = strs.len();
    let m = m as usize;
    let n = n as usize;
    let values = strs.iter().fold(vec![], |mut values, str| {
        let tuple = str.chars().fold((0, 0), |mut tuple, ch| {
            if ch == '0' {
                tuple.0 += 1;
            } else {
                tuple.1 += 1;
            }
            tuple
        });
        values.push(tuple);
        values
    });

    let mut dp = vec![vec![0; n + 1]; m + 1];
    for i in 1..=len {
        let (zero, one) = values[i - 1];
        for j in (zero..=m).rev() {
            for k in (one..=n).rev() {
                dp[j][k] = cmp::max(dp[j][k], dp[j - zero][k - one] + 1);
            }
        }
    }

    dp[m][n]
}