【代码随想录】刷题笔记Day44

2024-01-03 13:49:54

前言

  • 刚考完工程伦理的考试,虽然只有10道选择但真不是能通过常理去做的,还好周围全是大佬,拿个八九十分应该可以。另外,感觉身边的人刷题速度都好快啊,一对比就容易焦虑着急,还是慢慢来吧,一件事一件事做好

474. 一和零 - 力扣(LeetCode)

  • 二维的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);
    • 对比一维的01背包递推公式,zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])
  • 初始化
    • dp[0][0]初始化为0,其他也为0(取max保证不被覆盖就行)
  • 遍历顺序
    • 先物品(得到0和1的字符数)再背包(两层for循环,从后往前)
  • 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];
        }
    };

完全背包理论基础

  • ?物品有无限个,和01的差别就是变成正序遍历,同时注意组合和排列的差别
  • // 01背包问题
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
  • // 完全背包问题(先物品再背包,组合数)
    for(int i = 0; i < weight.size(); i++) { // 正序遍历物品
        for(int j = weight[i]; j <= bagWeight ; j++) { // 正序遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    
        }
    }
  • // 完全背包问题(先背包再物体,排列数)
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 0; i < weight.size(); i++) { // 遍历物品
            if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        cout << endl;
    }

518. 零钱兑换 II - 力扣(LeetCode)

  • 类似01背包的目标和,只是变成完全背包组合数的遍历顺序
  • 装满j的背包有dp[j]种方法;dp[j] += dp[j - coins[i]];dp[0] = 1
  • class Solution {
    public:
        int change(int amount, vector<int>& coins) {
            vector<int> dp(amount + 1, 0);
            dp[0] = 1;
            for (int i = 0; i < coins.size(); i++) { // 遍历物品
                for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                    dp[j] += dp[j - coins[i]];
                }
            }
            return dp[amount];
        }
    };

?后言

  • 不想干活不想干活不想干活,毫无正反馈,刷题and学习收获知识多快乐呀呜呜

文章来源:https://blog.csdn.net/qq_56077562/article/details/135358329
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。