【力扣刷题 | 第二十五天】

你的名字 2023-10-14 16:21 38阅读 0赞

![935aae90b9714fb9b4fa40a951f4c20e.jpeg][]

**目录**

前言：

474. 一和零 - 力扣（LeetCode）

总结:

--------------------

## 前言： ##

今天我们依旧暴打动态规划

## [474. 一和零 - 力扣（LeetCode）][474. _ - _LeetCode] ##

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

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

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

![ed03e0c2031e42f18695e3c4672d3d0d.png][]

其实这也是一个背包问题，只不过以前我们的限制条件只有一个重量，现在变成了两个，一个是，m，一个是n。那么我们就可以抽象的看他为一个二维的01背包问题。

那么我们就按照动态规划五部曲走：

1.确定dp数组的含义及其下标方式：dp\[i\]\[j\] 表示装满 i 个0 和 j 个1 的背包中的最大子集长度

class Solution {
    public:
        int findMaxForm(vector<string>& strs, int m, int n) {
                vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); 
            for (string str : strs) { 
                int one = 0, zero = 0;
                for (char c : str) {
                    if (c == '0') zero++;
                    else one++;
                }
                for (int i = m; i >= zero; i--)
                 { 
                    for (int j = n; j >= one; j--) 
                    {
                        dp[i][j] = max(dp[i][j], dp[i - zero][j - one] + 1);
                    }
                }
            }
            return dp[m][n];
        }
        
    };

## 总结: ##

动态规划很难一眼看出来就是背包问题，要仔细甄别

如果我的内容对你有帮助，请**点赞，评论，收藏**。创作不易，大家的支持就是我坚持下去的动力！

![69e9169c980f43e0aad31ff9ada88a9c.png][]

[935aae90b9714fb9b4fa40a951f4c20e.jpeg]: https://img-blog.csdnimg.cn/935aae90b9714fb9b4fa40a951f4c20e.jpeg
[474. _ - _LeetCode]: https://leetcode.cn/problems/ones-and-zeroes/
[ed03e0c2031e42f18695e3c4672d3d0d.png]: https://img-blog.csdnimg.cn/ed03e0c2031e42f18695e3c4672d3d0d.png
[69e9169c980f43e0aad31ff9ada88a9c.png]: https://img-blog.csdnimg.cn/69e9169c980f43e0aad31ff9ada88a9c.png