代码随想录算法训练营第46期Day37,38,39,41-而m 和 n相当于是一个背包,两个维度的背包。 理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。 但本题其实是01背包问题! 只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。 开始动规五部曲: 确定dp数组(dp table)以及下标的含义 dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。 确定递推公式 dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。 dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。 然后我们在遍历的过程中,取dp[i][j]的最大值。 所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); 此时大家

因为对于二维dp,dp[i][j]都是通过上一层即dp[i - 1][j]计算而来,本层的dp[i][j]并不会被覆盖!

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;
            for (char c : str) {
                if (c == '0') zeroNum++;
                else 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];
    }
};

上一篇:Spring6梳理15——Bean的作用域


下一篇:【MySQL】设置二进制日志文件自动过期,从根源上解决占满磁盘的问题:通过修改 binlog_expire_logs_seconds 配置项-步骤