DP：01背包问题
一、背包问题的概述
背包问题是⼀种组合优化的NP完全问题。 本质上是为了找出“带有限制条件的组合最优解”
1、根据物品的个数，分为如下几类：
• 01背包问题：每个物品只有⼀个（重点掌握） • 完全背包问题：每个物品有无限多个（重点掌握） • 多重背包问题：每件物品最多有n个 • 混合背包问题：每个物品会有上⾯三种情况 • 分组背包问题：物品有n组，每组物品⾥有若⼲个，每组⾥最多选⼀个物品
2、根据背包是否装满，⼜分为两类
• 不⼀定装满背包（重点） • 背包⼀定装满（重点）
3、优化方案
• 空间优化：滚动数组（重点掌握） • 单调队列优化 • 贪心优化
4、根据限定条件的个数，⼜分为两类
• 限定条件只有⼀个：比如体积->普通的背包问题（重点） • 限定条件有两个：比如体积+重量->⼆维费用背包问题（重点）
5、根据不同的问法，⼜分为很多类：
• 输出方案 • 求方案总数 • 最优方案 • 方案可行性
背包问题的题型非常多样，其中最重要以及基础的就是01背包和完全背包以及背包是否装满的讨论（会通过牛客的两道模版题探究），还有滚动数组的优化策略（ 在以往的动态规划中，我们几乎很少去谈论空间优化，因为对于一道dp题来说，能解决出来就已经很不容易了，我们不太会关注其空间复杂度。但是在背包问题中，滚动数组的优化是有一定套路可言的，并且在某些情况下对时间也是有一定优化的！！）
二、01背包[模版]
滚动数组优化（空间复杂度N^2——>N 时间复杂度常数提升）
对于不存在的状态，因为我们该题中要求的是max，所以我们设成-0x3f3f3f3f保证该状态不被选到，设置成这个的原因是避免了越界的风险同时又保证了不存在的状态是小于0的，且不会影响填报！！
三、和为目标和的最长子序列长度
这题就是非常明显的01背包问题，其中每个数只有选或者不选，目标值相当于是容量，且要刚刚好。 dp[i][j]表示从前i个数选，和恰好为j的最长子序列。
滚动数组优化：
四、分割等和子集（需转化）
该题并不能直接用01背包问题，首先需要先将问题进行转化——在数组中选一些数，让这些数的和为sum/2。
滚动数组优化：
五、目标和（需转化）
滚动数组优化：
六、最后一块石头的重量||(需转化)
滚动数组优化：
七、将一个数字表示成幂的和的方案数
知识点1：double不支持取模，需要取模又担心溢出只能使用long long
知识点2：pow函数是求数的任意次幂
知识点3:10^9+7相当于1e9+7
滚动数组优化：
腾讯云开发者
