01背包问题总结

首先，需要清楚的是0/1背包问题本身：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

此处使用动态规划求解，问题的划分方式为：使用一个二维数组对问题进行两部分的划分。对于 dp[i][j] 求解的是，当背包容量为 j 时，在物品 0-i 中选择能够获取到的最大的容量。

那么在采取逐行遍历的方式，就是每一次增加物品的数量，递推公式为： dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i])

采取逐列遍历的方式，每一次增加的是背包的容量，那么递推公式为： dp[i][j]=max(dp[i][j],dp[i-1][j-weight[i]]+value[i])

使用滚动数组实现动态规划的过程：基于背包容量的滚动数组实现，那么此处就一定要先遍历物品再遍历背包了，因为动态规划数组的含义是，在第 i 次迭代中，使用 0-i 个物品去填充背包，能够得到的背包中物品的最大价值。并且是0/1背包问题，那么对于背包的遍历顺序一定要是

能否基于物品数量的滚动数组实现：

1. 动态规划数组的定义：定义数组 dp[n] ，在初始时表示，当背包容量为0时，能够装下的最大的物品价值。

2. 动态规划数组的推导：对于第 j 次迭代时，表示当背包容量为 j 时，能够装下的物品的最大价值。在一维的情形下，背包容量减去 weight[i] 的情形无法实现递推。

因此在0/1背包中使用滚动数组，只能基于背包容量的数组来实现。

动态规划

此处就是一个完全背包问题，但是背包的最优化问题是最多的方案数。并且在题中指出了，顺序不同的序列将会被视为不同的组合，也就是此处元素的选择上是有序的。那么采取滚动数组的方式来实现，需要先遍历背包，再遍历元素，因为只有这样才能保证选取上的有序。

1. 动态规划数组的定义：定义数组 dp[target+1] 表示总和为 target 的元素选择方案个数。

2. 动态规划数组的推导：在 j 次迭代中，从元素 0-n 中进行选择，那么相较于前面的方案，主要是背包容量增大。那么 dp[j]=dp[j]+dp[j-nums[i]]

3. 动态规划数组的初始化：在初始时，装满 dp[0] 的方案有一种，那么 dp[0]=1

4. 动态规划数组的遍历顺序：此处是先遍历背包再遍历物品，那么先从前向后遍历背包再从前向后遍历物品。

5. 举例验证：对于 nums={1,2,3} , target=4 动态规划的过程为:

dp={1,0,0,0,0}
dp={1,1,0,0,0}
dp={1,1,2,0,0}
dp={1,1,2,4,0}
dp={1,1,2,4,7}

动态规划

本题是一个经典的完全背包的变体，此时背包的容量就是 amount ，物品的重量为 coins ，求解物品将背包装满的方案数。不同于之前0/1背包问题的变体（494.目标和），此处的硬币数量是无限的，并且是完全对于硬币做加法的。

那么这样的完全背包问题就适用于动态规划求解：

1. 动态规划数组的定义：定义数组 dp[amount+1] 表示在背包容量为 amount 时，将背包装满的方案数

2. 动态规划数组的推导：在第 i 次迭代中，考虑元素 coins[i] ，可以选取 0/n 个元素 coins[i] ，那么递推公式为 dp[j]=dp[j]+dp[j-coins[i]]

3. 动态规划数组的初始化：在初识时在元素 coins[0] 中选取元素尝试装满背包，那么对于元素 coins[0] 的倍数容量的背包就都能够被装满，也就是存在一种可行的方案。 for(int i=0;i*coins[0]<=amount;i++) dp[i*coins[0]]=1;

4. 动态规划数组的遍历顺序：此处采取先遍历硬币再遍历背包的方式，遍历的顺序都是从前向后遍历。

5. 举例验证：对于 coins={1,2,5},amount=5 动态规划数组的变化为：验证正确

dp={1,1,1,1,1,1}
dp={1,1,2,2,3,3}
dp={1,1,2,2,3,4}

多重背包问题的关键：在于对于每一个物体可以选择多次，在基于滚动数组的实现中，为了避免重复选择同一元素，在对背包的内层循环过程中采取从右向左的方式。那么在完全背包中要实现重复选择只需要将背包的内层循环从左向右进行即可。

1. 动态规划数组的定义：定义数组 dp[W+1] 表示，容量为 W 的背包能够装下的物品的最高价值。

2. 动态规划数组的推导：每次尝试将元素 i 转入到背包中看能否使得价值上升 dp[j]=max(dp[j],dp[j-weight[i]]+value[i])

3. 动态规划数组的初始化：初始时，未将物品装入到背包中，背包中的价值全部为 0

4. 动态规划数组的遍历顺序：在内外层循环中，既可以先遍历物品也可以先遍历背包，但是不论是对物品还是背包容量的遍历都需要从前向后进行。对于先遍历物品再遍历背包的理解：不断增加背包可选择的物品，在每一次添加物品后可以选择0或n个当前物品，将全部的物品都考虑到之后所得就是当前背包能够得到的最有化解。对于先遍历背包再遍历物品的理解：不断增加的是背包的容量，对于每一个背包容量，求解的是小容量的完全背包问题。（本质上就是一个减少物品的个数，一个减少背包的容量，从两个角度去划分子问题）

动态规划

问题的要求：寻找数组的子集，在子集中最多包含 m 个 0 和 n 个 1 ，使得子集中的元素尽可能的多。

此处完全就是一个0/1背包问题，背包的容量为： m 个 0 和 n 个 1 ，每一个物品的价值都是1，要装下尽可能多的物品。将背包的维度从原本的一维情形转变成了2维。

1. 动态规划数组的定义：定义数组 dp[m+1][n+1] ，其中 dp[i][j] 表示能装 i 个 0 、 j 个 1 的背包能够放下的物品个数。

2. 动态规划数组的推导：在第 k 次迭代中，在 0-k 个元素中进行选择，相较于上一次迭代，新增了第 k 个元素，记第 k 个元素中 0 的个数为 ， 1 的个数为 ，此处有两种情况：可以选择元素 k ，或者不选元素 k ，应该在两者之中选择能够装下最多元素数量的情形，那么递推公式为：

   $$dp[i][j]=max(dp[i-k_0][j-k_1]+1,dp[i][j])$$

3. 动态规划数组的初始化：在初始状态仅在元素 0 中进行选择，那么对于 dp[m][n] 首先全初始化为 0 ，对与 的

4. 动态规划数组的遍历顺序：外层循环将元素逐个加入，从左向右遍历元素数组 strs ，内层循环遍历动态规划数组，并且为了防止重复选择 i,j 都需要从大到小进行遍历。

对问题进行转化：

对整个数组 nums 进行求和，最终的和值为 ，假设在总体的表达式中前置符号为 的元素之和为 ，那么前置符号为 的元素之和为 ，那么就有 ，对问题进行转换就得到：

也就将问题转化为了，在数组 nums 中选取元素，是的元素的和等于 。上述假设都是建立在能够在数组 nums 中找到元素组合为表达式计算得到 target 的前提下，但若是不能找到任何方案，这样计算就会出现问题，因此需要增加一层判断，判断 是否存在余数，若是存在余数说明不存在任何方案。

1. 动态规划数组的定义：定义数组 dp[neg+1] 其中 dp[i]=j 表示，在 0-0 个元素中选取总和为 i 的方案有 j 种。

2. 动态规划数组的推导：在第 k 次迭代中，从 0-k 个元素中进行选取，此处相较于上一次，仅有 nums[k] 这个元素，不同，对应两种方式：选取或不选。那么递推公式 dp[i]=dp[i]+dp[i-nums[k]] if i-nums[k]>=0 else dp[i]

3. 动态规划数组的初始化：初始时全部初始化为0，然后 dp[nums[0]]=1(if nums[0]<=neg),dp[0]=1 。

4. 数组的遍历顺序：在外层循环中将数组中的元素逐个添加，因此外层循从左向右遍历的数组，在内层循环中则是遍历动态规划数组，在计算 dp[i] 时需要使用 dp[i-nums[k]] 的值，从右向左遍历。

5. 举例验证： nums={2,1},target=1 那么 neg=1 初始时 dp={1,0} 第一次迭代：dp[1]=dp[1]+dp[0]=1 验证正确。

动态规划

此处的题设中，对于石头选取的要求是任意选取，但是要求返回的内容是最后剩余石头的最小可能重量，本质上还是在求解问题的最优解。

重点还是在于问题的划分。首先，需要对问题进行转换，将上述问题转化为：将石头分为重量作为接近的两堆，那么最后剩余的最小石头重量就是两堆石头重点之间的差值，并且对于两堆石头的数量没有任何要求。

假设第一堆石头为： 第二堆石头为 ，那么首先 做相减，若是 消去后将剩余的元素 加入到石堆 中，那么下一次就在 中选择 和 的值进行消去。反之，则在 中进行选择。相等则同时消去两个。交替进行，最后两堆只会剩下一个或零个的元素。

动态规划

此处是集合的划分，要求划分的两个集合中元素的和相等。此处可以将问题转化为两个背包，并且两个背包的容量相同，都等于集合中全部元素总和的一半。那么子集划分的过程，也就是向背包中放入相应元素的过程，若是能将一个背包装满，那么另外一个也就一定能够装满。首先求得集合中全部元素的总和 2n 。

1. 动态规划数组的定义：初始的 dp[i] 表示在元素 0-0 中，背包容量为 i 时，能否恰好将背包装满。能够装满则为 true 不能为 false

2. 动态规划数组的推导：在第 i 次迭代时，在元素 0-i 中进行选择，此处仅有两种情况，选取元素 i 或者不选取元素 i 。那么 dp[j]=dp[j-nums[i]]||dp[j]

3. 动态规划数组的初始化：在初始时，dp[i] 表示在元素 0-0 中，背包容量为 i 时，能否恰好将背包装满。那么先全部初始化为 false ，若是 nums[0]<=n 则令 dp[nums[0]]=true ，并且对于背包容量为 0 时，本身就是满的，因此 dp[0]=true;

4. 动态规划数据的遍历顺序：外层循环，是对元素个数进行遍历，不断增加可以放入背包的元素数量，从 i=1,...,nums.size()-1 进行遍历，内层循环是对 dp 数据进行遍历，并且dp数组的遍历过程是从右向左进行的。并且在遍历的过程中只要出现 dp[n]==true 即可提前结束循环。

5. 举例验证：对于 nums = [1,5,11,5] 那么 dp 数组的长度为 12 初始化为 dp[1]=true 其他都为 false ，然后开始循环，第一遍循环： dp={1,1,0,0,0,1,1,0,0,0,0,0} ，第二遍循环 dp={1,1,0,0,0,1,1,0,0,0,0,1} 循环提前结束，验证正确。

01背包问题

有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight[i] ，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

此处最简单的方式就是使用回溯法去暴力求解：每一个物品有且仅有两种状态，放入背包或不放入背包，时间复杂度 。

使用动态规划进行求解，削减时间复杂度：此处的重点依旧在于问题的划分上。

动态规划

此处要使用动态规划进行求解，首先需要完成对于问题的划分。要找到 1-n 个节点对应的不同形态得到二叉搜索树，那么最简单的划分方式就是：分别以 1-n 做根节点去建立树。

从 n=3 出发：

1. 前两棵树：就是将 1 作为根节点去建立树，右子树有两个节点，并且这两个节点的布局就和 n=2 时对应的二叉搜索树的布局相同。此处，将问题换一种方式去理解：给定一个整数 n ，求解的是 n 个数组成的二叉搜索树有多少种，但是不要求是 1-n 的数，仅仅是升序的 n 个数。左子树有0个节点，节点的布局就和 n=0 时对应的二叉搜索树的布局相同（与就是一棵空树）。那么此处就能够将 n=3 的情形与 n=2，0 情形建立联系。

2. 第三课树：将 2 作为根节点去建立树，左边一个节点，和 n=1 时对应的二叉搜索树的布局相同，右边一个节点，和 n=1 时对应的二叉搜索树的布局相同。那么此时就是将 n=3 与 n=1 情形建立联系。

3. 后两棵树：将 3 作为根节点去建立树，右子树有0个节点，节点的布局就和 n=0 时对应的二叉搜索树的布局相同（与就是一棵空树）。左子树有两个节点，并且这两个节点的布局就和 n=2 时对应的二叉搜索树的布局相同。那么此处就能够将 n=3 的情形与 n=2，0 情形建立联系。