今天主要看了DP，前几天频繁遇到DP打击有点大。。
1. 0-1背包问题
要点：
a. 三部曲：
1. 状态和选择
状态：物品序号、背包容量
选择：放、不放
2. dp数组定义、base case
dp[i][w] 对于前i个物品，当前背包容量是w，这种情况下最大价值是dp[i][w]
比如dp[3][5] = 6，对于给定的一系列物品中，如果只前3个物品做选择，当背包容量是5时，最多可以装下的价值是6
3.根据【选择】，思考状态转移逻辑
第i个物品装入背包
dp[i][w] = dp[i-1][w-wt[i-1]] + value[i-1]
第i个物品不装入背包
dp[i][w] = dp[i-1][w]
注：i表示第i个，所以value[i-1]表示第i个物品价值
2. 0-1背包问题变体: 子集划分
101 分割等和子集
要点：
a. 往01背包上靠：因为要一分为2，所以只考虑一半，另一半自然会满足。即把sum/2看作是背包容量
b. dp[i][sum/2] 表示在容量sum/2的背包下，是否恰好能装满，dp数组装的是 [是否] 不再是 [大小]，这也说明dp数组含义非常重要
c. base case要注意：dp[..][0] = true，表示在容量0时，已经装满了
3.回溯和动规谁是谁爹
102 目标和
要点：
1.这题我用回溯从n到-1写的有问题，答案从0到n没有问题，没明白为什么
2.消除重叠子问题：
如何发现重叠子问题？看状态是否可能重复，
备忘录 key处理技巧，拼接字符串一定要加个,
然后dp也是，这个base case好难想啊，是不是划分子集问题的dp[..][0]都是1/true?
我错写成dp[..][0] = 0了，实际dp[..][0] = 1，给的解释居然是 “因为如果背包的最大载重为 0，「什么都不装」就是唯一的一种装法。“
目标和这个题目，用dp写，细节实在太多了
int[]
求和 Arrays.stream(int[]).sum()
求最值Arrays.stream(int[]).max().asInteger()