[数据结构与算法]LeetCode 动态规划问题

目录

474. 一和零

给定 m 个数字 0 和 n 个数字 1，以及一些由 0 1 构成的字符串，求利用这些数字最多可以构成多少个给定的字符串，字符串只可以构成一次。

示例：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {“10”,“0001”,“1”,“0”} ，因此答案是 4，其他满足题意但较小的子集包括 {“0001”,“1”} 和 {“10”,“1”,“0”} 。{“111001”} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

这是一个多维费用的 0-1 背包问题，有两个背包大小，0 的数量和1 的数量。可利用空间压缩将三维空间压缩到二维。

class Solution {
public:
    pair<int, int> count(const string& str) {
        int count0 = str.length(), count1 = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str[i] == '1') {
                --count0;
                ++count1;
            }
        }
        return make_pair(count0, count1);
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        int num = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (const string& str : strs) {
            auto [count0, count1] = count(str);
            for (int i = m; i >=count0; i--) { // 逆序遍历背包的容量
                for (int j = n; j >= count1; j--) {
                	// 递归最大组合数 
                    dp[i][j] = max(dp[i][j], dp[i - count0][j - count1] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

使用三维空间不压缩的情况

int findMaxForm(vector<string>& strs, int m, int n) {
    int num = strs.size();
    vector<vector<vector<int>>> dp(num + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
    for (int i = 1; i <= num; i++) {
        const string& str = strs[i - 1];
        auto [count0, count1] = count(str);
        // 此处的 0-1 背包问题每种物品的体积可以为 0，所以从 0 开始遍历
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (j >= count0 && k >= count1) {
                    // 是否取第i串的最优化选择
                    // 0-1 背包问题，有没有取当前 i 都需要考虑 i-1 时的情况
                    // 完全背包问题，当前 i 可能取多次，所以考虑 i-1 和 i 时的情况
                    dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - count0][k - count1] + 1);
                } else {
                    dp[i][j][k] = dp[i - 1][j][k];
                }
            }
        }
    }
    return dp[num][m][n];
}