leetcode动态规划之01背包系列

01背包基础
416 分割等和子集
题目：给个数组nums，判断能否分割成两个和相等的子集，返回true or false
给定背包容量target，能不能装满这个背包

解析：
先把给定数组的和求出来，对2取模等于1的直接返回法false，因为必然不可能得出来两个相等的子集；再除以2求出target；需要理解下什么是target，目前看来先是最后要用于比较的结果，其次对于背包问题来说，是背包的大小（容量）
1.dp数组确定及其含义：
dp[j]表示在背包的容量为j的时候，放入物品后，背包最大重量为dp[j]
2.确定递推公式：
dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
物品的重量是nums[i]，价值也是nums[i]
3.初始化为0
4.遍历顺序：物品外层，背包内层且倒序

494 目标和
题目：给定数组nums和target，在每个数字前放“+”或“-”，最后等于target的有多少种方法
给定背包容量，求装满背包有多少种方法

解析：
得先有点数学推导：所有的加号子集和为sum§，减号子集和为sum(q)，则有sum§ - sum(q) = target（注，这里本身不带符号，比如sum§ = 5, sum(q) = 3, target = 2）;
sum§ + sum(q) = sum
则有：sum§ + sum(q) + (sum§ - sum(q) ) = sum§ + sum(q) + target
左边为2 * sum§, 右边为sum + target
有sum§ = (sum + target) / 2（求出来的就是背包大小）
因为要除以2后成立，一定得是偶数

1.dp数组确定及其含义：
dp[j]表示在背包的容量为j的时候，填满背包有dp[j]种方法
2.确定递推公式：
dp[j] += dp[j - nums[i]] (求组合类的问题一般都是这个公式)
3.初始化为dp[0] = 1，不然后面都是0了
4.遍历顺序：物品外层，背包内层且倒序