数据结构学习 Leetcode474 一和零

关键词：动态规划 01背包

一个套路：

• 01背包：空间优化之后dp【target+1】，遍历的时候要逆序遍历
• 完全背包：空间优化之后dp【target+1】，遍历的时候要正序遍历

---

?

目录

题目：

思路：

复杂度计算：

代码：

---

题目：

?

思路：

这题能想到用01背包并正确用起来有点难哦！

这里面有三样东西，一些strs，m个0和n个1。

我刚开始是希望把strs当作容器，把0和1装进strs这个容器里，但是不行。

转换思路：把m个0和n个1作为两个容器，strs里的0和1分别装进这两个容器里。

因为有两个容器，所以dp得要两个维度dp[m+1][n+1]

其他都和一维的01背包一样

状态：dp[j][k] 前i个str中，使用?j个?0?和?k?个?1?的情况下最多可以得到的字符串数量。

转移方程：dp[j][k]=max(dp[j][k],dp[j-zeros][k-ones]+1)【zeros、ones：第i个str0和1的个数】

• 如果选dp[j][k]：不要第i个str，维持上一个str的状态。
• 如果选dp[j-zeros][k-ones]+1：要第i个str，数量+1。

初始化：dp[j][k]=0 因为是求最大

复杂度计算：

时间复杂度O(lmn+L) l=strs.size() L=所有str的字符总数（统计了每个str的01数量）

空间复杂度O(mn)

代码：

class Solution {
public:
    int findMaxForm(std::vector<std::string>& strs, int m, int n) {
        
        std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1));
        for (const auto& str:strs)
        {
            int zeros = 0, ones = 0;
            for (const auto& c : str)
            {
                if (c == '0')++zeros;
                else ++ones;
            }
            for (int j = m; j >= zeros; --j)
            {
                for (int k = n; k >= ones; --k)
                {
                    dp[j][k] = std::max(dp[j][k], dp[j - zeros][k - ones] + 1);
                }
            }
        }
        return dp[m][n];
    }
};