企业官网建设流程全解析

LeetCode 474：一和零（Ones and Zeroes）—— 题解 ✅

🔗 题目链接

👉 https://leetcode.cn/problems/ones-and-zeroes/

📖 内容概要

给定一个二进制字符串数组strs，以及两个整数m和n，
请你找出并返回strs的最大子集大小，使得子集中：

• '0'的总数不超过m
• '1'的总数不超过n

✅ 二维 0/1 背包
✅ 字符串视为物品
✅ 面试高频 / Medium-Hard 过渡题

💡 解题思路（核心）

一、问题本质

每个字符串：

• 消耗一定数量的0
• 消耗一定数量的1
• 价值为1

👉在二维资源限制下，最多能选多少个字符串

✅ 标准的二维 0/1 背包问题

二、状态定义

dp[i][j]=使用不超过 i 个0和 j 个1，能组成的最大字符串数量

三、状态转移方程

设当前字符串消耗：

• x个'0'
• y个'1'

dp[i][j]=max(dp[i][j],dp[i-x][j-y]+1)

✅ 选或不选当前字符串
✅ 必须倒序遍历（0/1 背包）

四、初始化

int[][]dp=newint[m+1][n+1];

默认值0即可。

✅ AC 代码（Java）

classSolution{publicintfindMaxForm(String[]strs,intm,intn){int[][]dp=newint[m+1][n+1];for(Strings:strs){intx=0,y=0;// 统计 0 和 1 的数量for(charc:s.toCharArray()){if(c=='0')x++;elsey++;}// 二维 0/1 背包for(inti=m;i>=x;i--){for(intj=n;j>=y;j--){dp[i][j]=Math.max(dp[i][j],dp[i-x][j-y]+1);}}}returndp[m][n];}}

⏱️ 复杂度分析

🔍 与其他背包题的对比

✅ 一句话总结

把每个字符串看成“消耗 0 和 1 的物品”，在二维背包容量下求最大个数。

📌 面试加分点（建议记住）

• ✅ 为什么是二维 DP？
• ✅ 为什么必须倒序遍历？
• ✅ 为什么价值是1而不是字符串长度？
• ✅ 与“最多硬币数”问题的相似性