[474]. 一和零

[474]. 一和零

• • 题目
  • 算法设计：动态规划

 

---

题目

• 题目：[474]. 一和零

 

---

算法设计：动态规划

背包建模：

• 背包的容量是谁，有俩个容量，m 个 0、n 个 1，有俩个维度的 01 背包。
• 背包的物品是谁，数组里面的字符串，每个字符串的价值都是 1，成本是该字符串中 1 的数量和 0 的数量。
• 背包的选取方式是什么，在 1 的数量是 m，0 的数量是 n 的条件下，最大价值是多少。

 

设计状态：

• dp[k][i][j]：代表考虑前 k 件物品，在数字 1 容量是 i，数字 0 容量是 j 的条件下的「最大价值」。

设计状态转移方程：

• 不选当前字符串：dp[k][i][j] = dp[k-1][i][j]
• 选当前字符串：dp[k][i][j] = max( dp[k-1][i][j], dp[k-1][i-当前字符串使用 1 的个数][j-当前字符串使用 0 的个数] + 1 )

事实上，我们还能继续进行空间优化。

再次观察我们的「状态转移方程」发现：f[k][i][j] 不仅仅依赖于上一行，还明确依赖于比 i 小和比 j 小的状态。

即可只依赖于「上一行」中「当前列」的格子，和「前面列」的格子。

因此可直接参考「01 背包的空间优化」方式：

• 使用一维数组 + 倒推，取消掉「物品维度」

状态表达：

• dp[i][j]：最多有 i 个 0 和 j 个 1 的 $strs$ 的最大子集的大小为 dp[i][j]。

状态转移方程：

• $dp[i][j]=max(dp[i][j],dp[i-zeroNum][j-oneNum]+1)$

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
        for (string str : strs) {               // 遍历当前物品
        
            int oneNum = 0, zeroNum = 0;        // 记录当前物品的 1、0 的数量
            for (char c : str) 
                c == '0' ? zeroNum++ : oneNum++;
            
            for (int i = m; i >= zeroNum; i--)  // 从后向前遍历背包容量 
                for (int j = n; j >= oneNum; j--) 
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
        }
        return dp[m][n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17