01背包理论基础
【二维数组】
1.确定dp数组以及下标的含义
dp[i][j]的定义为：[0-i]之间的物品任取，放进容量为j的背包里
2.确定递推公式
分两种情况：
放物品i:
dp[i-1][j-wight[i]]+value[i]
当背包容量为j-weight[i]的时候不放物品i的最大价值
不放物品i:
dp[i-1][j]
当背包容量为j的时候不放物品i的最大价值
综合两种情况考虑：
dp[i][j] = max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
3.确定dp数组如何初始化
1.将dp[i][0]全部初始化为0
意思是当背包容量为0的时候，背包什么也放不了，因此总价值是0
2.将dp[0][j]全部初始化为物品0的价值
意思是当背包只放物品0的时候，总价值就只为物品0的价值
注意：当物品0的重量大于背包容量的时候，应该将背包价值初始化为0（因为放不下）
3.非零下标的初始化：
初始化成什么都可以，因为非零下标全是根据前面的数值推导出来的，所以初始化成什么都不影响结果
4.确定遍历顺序
两层for循环：
第一层遍历物品：
第二层遍历背包容量：
递推公式
注意：对于二维数组实现的背包问题，其实先遍历物品还是先遍历背包容量都可以
因为我们当前数据总是由左上方和正上方的值推导出来的，只要确保左上方和正上方有值，遍历顺序就无所谓
5.举例推导dp数组
手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的
【一维数组】
01背包理论基础（滚动数组）
1.确定dp数组以及下标的含义
dp[j]的定义为：容量为j的背包最大价值为dp[j]
2.确定递推公式
分两种情况：
放物品i:
dp[j-weight[i]]+value[i]
当背包容量为j-weight[i]的时候不放物品i的最大价值
不放物品i:
dp[j]
当背包容量为j的时候不放物品i的最大价值
综合两种情况考虑：
dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
3.确定dp数组如何初始化
dp[0]=0
意思是背包容量为0的时候，背包价值为0
非零下标应该初始化为非负数里的最小值，因为我们需要不断地进行比较，取最大值更新
4.确定遍历顺序
两层for循环：
第一层遍历物品：
第二层遍历背包容量：
递推公式
注意：因为一维数组每一层的数据是需要重复利用的，因此遍历顺序只能是倒序遍历
我们需要倒序来保证每个物品添加一次，因为需要保证每个物品只添加一次，所以必须先遍历物品，再遍历背包
5.举例推导dp数组
手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的
LeetCode 416 分割等和子集
题目链接：416. 分割等和子集 - 力扣（LeetCode）
【解题思路】
可以把本题抽象成一个背包问题，每个数值就是价值和重量，我们装满[target]背包的价值=target就代表找到了
1.确定dp数组以及下标的含义
dp[j]的定义为：容量为j的背包最大价值为dp[j]
2.确定递推公式
dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
因为重量和价值都是nums[i]
3.确定dp数组如何初始化
dp[0]=0
意思是背包容量为0的时候，背包价值为0
非零下标应该初始化为非负数里的最小值，因为我们需要不断地进行比较，取最大值更新
4.确定遍历顺序
两层for循环：
第一层遍历物品：
第二层遍历背包容量：
递推公式
注意：因为一维数组每一层的数据是需要重复利用的，因此遍历顺序只能是倒序遍历
我们需要倒序来保证每个物品添加一次，因为需要保证每个物品只添加一次，所以必须先遍历物品，再遍历背包
5.举例推导dp数组
手动推导一下答案，然后将数组打印出来，看看每个状态是否是按照我们的思路进行转移的
【解题步骤】
1.如果数组为空，或者数组长度为0，则return false
2.新建一个sum变量，统计nums数组的总和
3.如果总和为奇数，则不能平分，return false
4.定义一个target，初始化为总数的一半
5.定义一个dp数组，长度为target+1
6.先遍历物品，i<nums.length时停止遍历
再遍历背包，j>=nums[i]时停止遍历
运用递推公式更新dp[j]
如果dp[target]=target，说明已经找到，无需再遍历，return true
8.return dp[target] == target