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

发布时间:2024年01月05日

前言

  • 刚考完自辩,Chat回答举例什么的真方便。早上做组会PPT去了,火速来刷题!

139. 单词拆分 - 力扣(LeetCode)

  • 单词是物品,字符串s是背包,单词能否组成字符串s,就是问物品能不能把背包装满
  • 能重复用,是完全背包,其实也就是双指针的思想,i从头到尾,j从0到i
  • dp[i]含义
    • 从头开始字符串长度为i,dp[i]为true表示可以拆分为在字典中出现的单词
  • 递推公式
    • if( [j, i] 这个区间的子串出现在字典里 && dp[j]==true)? dp[i] = true
  • 初始化
    • dp[0] = true, 其他为false
  • 遍历顺序
    • 讲究顺序,用完全背包排列数的顺序,先背包后物品(双指针)
  • class Solution {
    public:
        bool wordBreak(string s, vector<string>& wordDict) {
            unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
            vector<bool> dp(s.size() + 1, false);
            dp[0] = true;
            for (int i = 1; i <= s.size(); i++) {   // 遍历背包
                for (int j = 0; j < i; j++) {       // 遍历物品(其实是子串的开始下标)
                    string word = s.substr(j, i - j); //substr(起始位置,截取的个数)
                    if (wordSet.find(word) != wordSet.end() && dp[j]) {
                        dp[i] = true;
                    }
                }
            }
            return dp[s.size()];
        }
    };

多重背包理论基础

  • ?多重背包指的是有限个物品,其实把每个物品独立化后就是01背包问题了
  • for(int i = 0; i < n; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包,然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }

?背包问题总结

?后言

  • 背包问题终于结束啦,感觉这几道顺下来还是有点眉目的,只要把思路理清楚其实代码啪啪啪就可以打出来了(主要是因为比较简短,要考虑的特殊情况不多),今天是周五!下班!!
文章来源:https://blog.csdn.net/qq_56077562/article/details/135411761
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。