代码随想录算法训练营day38|动态规划part6
前面几题思路较为简单，也与前几天的题目思路相似，在此不再赘述。重点是今天的最后一题，这题与前面几题的思路都不太一样，难度也比较大。139单词拆分这道题，应该将所给的字符串看作背包，将所给的字典序看作物品，所以这道题就可以转化为求解在所给的字符串中是否能用所给字典序将其填满。考虑采用unordered_set存储所给字典序以判断在字符串中的某个序列是否在所给字典序中。又因为在这题中，每个所给字符串的子序列都可以分割为更小的子序列直到不能再分割为止，所以只要某个子序列所分割后的两个子序列都能在所给字典序列中找到，那么这个子序列就满足题意。另外，关于这题是先遍历背包还是先遍历物品的问题，由于这题所给的字典序的顺序有要求，所以是排列问题，所以应该先遍历背包再遍历物品。
322. 零钱兑换
视频讲解：动态规划之完全背包，装满背包最少的物品件数是多少？| LeetCode：322.零钱兑换_哔哩哔哩_bilibili
279.完全平方数
本题 和 322. 零钱兑换 基本是一样的，大家先自己尝试做一做
视频讲解：动态规划之完全背包，换汤不换药！| LeetCode：279.完全平方数_哔哩哔哩_bilibili
139.单词拆分
视频讲解：动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分_哔哩哔哩_bilibili
关于多重背包，你该了解这些！
背包问题总结篇！
原文地址：https://blog.csdn.net/aaal1234/article/details/144385496
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！