系列文章目录
代码随想录算法训练营第一天|数组理论基础，704. 二分查找，27. 移除元素
代码随想录算法训练营第二天|977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II
代码随想录算法训练营第三天|链表理论基础，203.移除链表元素，707.设计链表，206.反转链表
代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，总结
代码随想录算法训练营第五天|哈希表理论基础，242.有效的字母异位词，349. 两个数组的交集，202. 快乐数，1. 两数之和
代码随想录算法训练营第六天|454.四数相加II，383. 赎金信，15. 三数之和，18. 四数之和，总结
代码随想录算法训练营第七天|344.反转字符串，541. 反转字符串II，卡码网：54.替换数字，151.翻转字符串里的单词，卡码网：55.右旋转字符串
代码随想录算法训练营第八天|28. 实现 strStr()，459.重复的子字符串，字符串总结，双指针回顾
代码随想录算法训练营第九天|理论基础，232.用栈实现队列，225. 用队列实现栈
代码随想录算法训练营第十天|20. 有效的括号，1047. 删除字符串中的所有相邻重复项，150. 逆波兰表达式求值
代码随想录算法训练营第十一天|239. 滑动窗口最大值，347.前 K 个高频元素，总结
代码随想录算法训练营第十二天|理论基础，递归遍历，迭代遍历，统一迭代
代码随想录算法训练营第十三天|层序遍历10，226.翻转二叉树，101.对称二叉树
代码随想录算法训练营第十四天|104.二叉树的最大深度，559.n叉树的最大深度，111.二叉树的最小深度，222.完全二叉树的节点个数
代码随想录算法训练营第十五天|110.平衡二叉树，257. 二叉树的所有路径，404.左叶子之和
代码随想录算法训练营第十六天|513.找树左下角的值，112. 路径总和，113.路径总和ii，106.从中序与后序遍历序列构造二叉树，105.从前序与中序遍历序列构造二叉树
代码随想录算法训练营第十七天|654.最大二叉树，617.合并二叉树，700.二叉搜索树中的搜索，98.验证二叉搜索树
代码随想录算法训练营第十八天|530.二叉搜索树的最小绝对差，501.二叉搜索树中的众数，236. 二叉树的最近公共祖先
代码随想录算法训练营第十九天|235. 二叉搜索树的最近公共祖先，701.二叉搜索树中的插入操作，450.删除二叉搜索树中的节点
代码随想录算法训练营第二十天|669. 修剪二叉搜索树，108.将有序数组转换为二叉搜索树，538.把二叉搜索树转换为累加树，总结篇
代码随想录算法训练营第二十一天|回溯算法理论基础，77. 组合
代码随想录算法训练营第二十二天|216.组合总和III，17.电话号码的字母组合
代码随想录算法训练营第二十三天|39. 组合总和，40.组合总和II，131.分割回文串
代码随想录算法训练营第二十四天|93.复原IP地址，78.子集，90.子集II
代码随想录算法训练营第二十五天|491.递增子序列，46.全排列，47.全排列 II
代码随想录算法训练营第二十六天|332.重新安排行程，51. N皇后，37. 解数独，总结
代码随想录算法训练营第二十七天|贪心算法理论基础，455.分发饼干，376. 摆动序列，53. 最大子序和
代码随想录算法训练营第二十八天|122.买卖股票的最佳时机II，55. 跳跃游戏，45.跳跃游戏II
代码随想录算法训练营第二十九天|1005.K次取反后最大化的数组和，134. 加油站，135. 分发糖果
代码随想录算法训练营第三十天|860.柠檬水找零，406.根据身高重建队列，452. 用最少数量的箭引爆气球
代码随想录算法训练营第三十一天|435. 无重叠区间，763.划分字母区间，56. 合并区间
代码随想录算法训练营第三十二天|738.单调递增的数字，968.监控二叉树，总结
代码随想录算法训练营第三十三天|动态规划理论基础，509. 斐波那契数，70. 爬楼梯，746. 使用最小花费爬楼梯
代码随想录算法训练营第三十四天|62.不同路径，63. 不同路径 II
代码随想录算法训练营第三十五天|343. 整数拆分，96.不同的二叉搜索树
代码随想录算法训练营第三十六天|背包理论基础，416. 分割等和子集
代码随想录算法训练营第三十七天|1049. 最后一块石头的重量 II，494. 目标和，474.一和零
代码随想录算法训练营第三十八天|完全背包，518. 零钱兑换 II，377. 组合总和 Ⅳ
代码随想录算法训练营第三十九天|70. 爬楼梯 （进阶），322. 零钱兑换，279.完全平方数
文章目录
- 系列文章目录
- 139.单词拆分
- 多重背包介绍
- 背包问题总结篇
139.单词拆分
题目链接： 139.单词拆分
题目内容： 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
视频讲解： 动态规划之完全背包，你的背包如何装满？| LeetCode：139.单词拆分
可以等同于完全背包问题：单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。拆分时可以重复使用字典中的单词，说明就是一个完全背包！
动态规划问题的五步曲：
-
确定dp数组（dp table）以及下标的含义：字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
-
确定递推公式：
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。 -
dp数组如何初始化：dp[0]一定要为true，非零下标默认为false
-
确定遍历顺序：这是背包里求排列问题，所以需先遍历背包，再遍历物品。
-
举例推导dp数组
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordset=set(wordDict)
n=len(s)
dp=[False]*(n+1)
dp[0]=True
for i in range(1,n+1): #遍历背包
for j in range(i): #遍历物品（单词）
if dp[j] and s[j:i] in wordset:
dp[i]=True
break
return dp[n]
多重背包介绍
多重背包的概念：
- 有N种物品和一个容量为V 的背包。
- 第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。
- 求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
每件物品最多有Mi件可用，如果把把Mi件摊开，其实就是一个01背包问题了。
背包问题总结篇
几种常见的背包：
动态规划五部曲：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
常见递推公式：
- 问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
- 问装满背包有几种方法：dp[j] += dp[j - nums[i]]
- 问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
- 问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
01背包的遍历顺序：
- 二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
- 一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
完全背包的遍历顺序：
- 纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
- 如果求最小数，那么两层for循环的先后顺序就无所谓了。
