LeetCode 474. 一和零

Categories:

题目描述
思路分析
1. 解法一：二维 0-1 背包（推荐）
相似题目

题目描述

✅ 474. 一和零

思路分析

解法一：二维 0-1 背包（推荐）

核心思路：

统计每个字符串中 0 和 1 的数量，视作一个物品的双维重量。

设 dp[i][j] 表示在最多 i 个 0、j 个 1 的限制下可选的最大字符串数量。

对每个字符串进行 0-1 逆序更新，避免重复使用同一字符串。

复杂度分析：

时间复杂度：O(L _ m _ n)，其中 L 表示字符串数量。

空间复杂度：O(m * n)，用于二维 DP 数组。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (String s : strs) {
            int zeros = 0;
            int ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') {
                    zeros++;
                } else {
                    ones++;
                }
            }

            // 0-1 背包逆序更新
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
}

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 _, s := range strs {
		zeros := 0
		ones := 0
		for i := 0; i < len(s); i++ {
			if s[i] == '0' {
				zeros++
			} else {
				ones++
			}
		}

		// 0-1 背包逆序更新
		for i := m; i >= zeros; i-- {
			for j := n; j >= ones; j-- {
				val := dp[i-zeros][j-ones] + 1
				if val > dp[i][j] {
					dp[i][j] = val
				}
			}
		}
	}

	return dp[m][n]
}

相似题目

题目	难度	考察点
416. 分割等和子集	中等	0-1 背包
494. 目标和	中等	0-1 背包
879. 盈利计划	困难	多维背包
518. 零钱兑换 II	中等	完全背包
377. 组合总和 Ⅳ	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/82171475