474. 一和零

Problem: 474. 一和零

思路

其实我真的会写了,但是我还是有点点不明白。

先遍历物品再遍历背包,看看这个物品装进去之后,子集大小相比与之前的物品装进去是否子集变大变大了。

dp[i][j]其实存了之前的物品装进去的子集大小。

dp[i][j] = std::max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);

下面是一个理解递推公式的例子：

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

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 zeroNum = 0, oneNum = 0;
            for (char& ch : str) {
                if (ch == '0') {
                    zeroNum += 1;
                } else {
                    oneNum += 1;
                }
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = std::max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
                }
            }
        }
        return dp[m][n];
    }
};