- 第 184 篇 -Date: 2026 - 03- 10 | 周二Author: 郑龙浩仟墨算法动态规划DP| 完全背包文章目录2026-03-10 周二 | 算法打卡day187-力扣139-单词拆分难度有点高【题目】【思路】**【困惑点1】不理解递推的条件**或者说是不理解什么时候确定s[0:i]是可以拆分为1个或多个wordDict中的单词的)【困惑点2】j作为分割点j算作左边的单词里还是右边的单词里决定了j的起始和结束位置【困惑点3】在动态规划的双重循环中当内层循环的 j固定为 0时这个情况到底在计算什么它的物理意义是什么以及为什么需要这个看起来“左边为空”的特殊分割点【代码】蓝桥云课-背包问题 2026-03-10 周二1-蓝桥云课303-求解01背包问题【题目】输入输出样例【思路】【代码】2-蓝桥云课304-求解完全背包问题2026-03-10 周二 | 算法打卡day187-力扣139-单词拆分难度有点高这道题对我来说特难理解的理解了很久才大概明白用了2个小时去理解和整理归纳才大概明白怎么做明天还是需要复习一下且之后有时间都应该复习一下重新刷一下这道题【题目】给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。**注意**不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。示例 1输入:s “leetcode”, wordDict [leet, code]输出:true解释:返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。示例 2输入:s “applepenapple”, wordDict [apple, pen]输出:true解释:返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。注意你可以重复使用字典中的单词。示例 3输入:s “catsandog”, wordDict [cats, dog, sand, and, cat]输出:false提示1 s.length 3001 wordDict.length 10001 wordDict[i].length 20s和wordDict[i]仅由小写英文字母组成wordDict中的所有字符串互不相同【思路】根据题意可以判断出这个题是个【完全背包】的技巧背包容量字符串s的长度物品字符串列表wordDict中的所有字符串每个字符串是一个物品物品质量wordDict中每个字符串的长度也就是字符串的长度就是该物品的质量物品价值无价值什么背包【完全背包】因为每个单词都可以重复也就意味着每个物品可以重复度目标物品能否正好装满背包dp[i]含义字符串长度为i时可以拆分为一个或多个在字典中出现的单词为true反之false这道题中如果想完全转换为【纯完全背包】去理解是有些困难的特别是在递推公式这块所以理解的时候就不要彻底转变了比如此前的完全背包都是遍历物品的这里遍历的不是物品而是分割线j让分割点从0开始尝试一直尝试到i【困惑点1】不理解递推的条件或者说是不理解什么时候确定s[0:i]是可以拆分为1个或多个wordDict中的单词的)注意s[0:j)和s[j:i)都是左闭右开的if(wordSet.find(word)!wordSet.end()dp[j]){dp[i]true;}第一部分wordSet.find(word) ! wordSet.end()检查从j到i的这个子串即s[j:i)是否直接存在于单词表wordDict中也就是说s[j:i)是否是最后一个“单词片段”第二部分dp[i]字符串从开头到位置j的这一整段即s[0:j)是否可以被拆分成一个或多个wordDict中的单词的如果dp[j]为true意味着s[0:j)这个“前半部分”已经整体上被成功拆分好了。它可能被拆成了好几个单词但无论如何它已经被证明是“可拆分的”只要满足以上两个条件就可以确定s[0:i]是可以被拆分为一个或多个wordDict中的单词的也就是可以执行dp[i] true;将其设置为true了总结什么情况下执行dp[i] trueor 总结什么时候确定s[0:i]是可以拆分为1个或多个wordDict中的单词的是否存在一个分割点j使得最后一段​s[j:i)本身就是一个单词在字典里前面整段​s[0:j)已经被证实是可以被拆分的dp[j] true【困惑点2】j作为分割点j算作左边的单词里还是右边的单词里决定了j的起始和结束位置注意s[0:j)和s[j:i)都是左闭右开的分割点j是算在右边要检查的单词里的更准确地说j是右边单词的起始索引这就导致了j的遍历是从0开始i - 1结束的因为j既然算作右边的单词里必须保证j右边至少有一个字母的【困惑点3】在动态规划的双重循环中当内层循环的j固定为0时这个情况到底在计算什么它的物理意义是什么以及为什么需要这个看起来“左边为空”的特殊分割点注意s[0:j)和s[j:i)都是左闭右开的当j0时意味着左边部分s[0:0]是一个空字符串。它的状态dp[0]在初始化时被设为true这是一个基石设定代表空字符串视为“可拆分”。右边部分候选单词s.substr(0, i-0)即从开头取i个字符也就是整个当前正在检查的子串s[0:i]。因此j0这种情况专门用于判断一个最简单的情形「 整个字符串s[0:i)本身是否直接就是字典里的一个单词 」也就是如果少了j0的情况也就少了一个s[0:i)本身就是一个字典里的单词的判断了【代码】/* 【7-力扣139-单词拆分】 算法完全背包 - 一维DP Author郑龙浩 Date2026-03-10 用时 */#includebits/stdc.husingnamespacestd;classSolution{public:boolwordBreak(string s,vectorstringwordDict){intlens.size();// dp[i]含义长度为i的字符串s[0:i)能否被拆分为字典中的单词vectorbooldp(len1,false);dp[0]true;// 没有含义是为了后面可以递推出正确的结果来unordered_setstringwordSet(wordDict.begin(),wordDict.end());// 存入set中方便find()for(inti1;ilen;i){// 不断尝试s[0:i)for(intj0;ji;j){// j是分割点且j本身也被当做右边的单词的起始字母// s.substr(j, i - j): 从下标j开始取出i - j个字符也就是直接将j到字符串s的最后一个字符全都取出来了string lastWords.substr(j,i-j);// s[0:i)中取出最后的单词可能的单词// wordSet.find(lastWord) ! wordSet.end(): 检查**从 j到 i的这个子串**即 s[j:i]是否直接存在于单词表wordDict中// dp[j] true: 字符串从开头到位置 j的这一整段即 s[0:j]是否可以被拆分成一个或多个wordDict中的单词的if(wordSet.find(lastWord)!wordSet.end()dp[j]true){// 检查j右边的字符串是否是wordDict中的1个单词 检查j左边的字符串是否是1个或多个wordDict中的单词dp[i]true;break;// 找到1种拆分方式即可不加beak其实也是正确的只是会多执行很多代码罢了}}}returndp[len];}};intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);return0;}蓝桥云课-背包问题 2026-03-10 周二1-蓝桥云课303-求解01背包问题【题目】【题目描述】实现一个算法求解 01 背包问题。背包问题的介绍如下已知一个容量为 totalweighttotalweight​ 的背包有不同重量不同价值的物品问怎样在背包容量限制下达到利益最大化。01 背包问题要求每个物品只有一个可以选择放入或者不放入背包。背包问题求解方法的介绍如下用符号 ViVi​ 表示第 ii 个物品的价值WiWi​ 表示第 ii 个物品的体积Vi,jVi,j​ 表示当前背包容量为 jj 时前 ii 个物品最佳组合对应的价值。对于当前第 ii 个商品如果包的容量比该物品体积小即 jWijWi​。那么此时的价值与前 i−1i−1 个的价值是一样的即 Vi,jVi−1,jVi,j​Vi−1,j​。对于当前第 ii 个商品如果包的容量能够装下该物品即 Wi≤jWi​≤j。此时需要判断装或者不装这个物品的价值对比选择使价值更大的情况即 Vi,jmax⁡(ViVi−1,j−Wi,Vi−1,j)Vi,j​max(Vi​Vi−1,j−Wi​​,Vi−1,j​)。通过最优解回溯法找到解的组成当 Vi,jVi−1,jVi,j​Vi−1,j​时说明没有选择第 ii 个物品。当 Vi,jVi−1,j−WiVi,j​Vi−1,j−Wi​​ 时说明装了第 ii 个商品。从 ijij 的最大值一直遍历到 i0i0 则找到了所有解。【输入描述】第一行为两个数字 totalweight、Ntotalweight​、N均不超过 1000。totalweighttotalweight​ 含义见题干NN 为物品数量。接下来 NN 行每行两个数字 WiWi​、ViVi​均不超过 1000。含义见题干。【输出描述】输出一行为在背包容量限制下的最大化利益。输入输出样例输入8 5 3 4 5 5 1 2 2 1 2 3输出10【思路】这就是一个【纯01背包问题】【代码】/* 【1-蓝桥云课303-求解01背包问题】 算法01背包 - 一维DP Author郑龙浩 Date2026-03-10 用时12min 56s 好久没做纯01背包题反倒忘记怎么写了稍微多花了几分钟才想起来 */#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intN,M;cinNM;vectorintW(M),V(M);for(inti0;iM;i){cinW[i]V[i];}vectorintdp(N1,0);for(inti0;iM;i){for(intjN;jW[i];j--){dp[j]max(dp[j],dp[j-W[i]]V[i]);}}coutdp[N];return0;}2-蓝桥云课304-求解完全背包问题/* 【2-蓝桥云课304-求解完全背包问题】 算法完全背包 - 一维DP Author郑龙浩 Date2026-03-10 用时10min */#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intN,M;cinNM;vectorintW(M),V(M);vectorintdp(N1,0);for(inti0;iM;i)cinW[i]V[i];for(inti1;iN;i){// 背包for(intj0;jM;j){// 物品if(W[j]i){dp[i]max(dp[i],dp[i-W[j]]V[j]);}}}coutdp[N];return0;}