代码随想录 (programmercarl.com)
1049. 最后一块石头的重量II
核心思路：将石头分成重量近似的两堆，与之前的416.分割等和子集问题很相似。
1.确定dp数组以及下标的含义
dp[j]表示容量为j的背包，最多可以背的最大重量为dp[j]。
其中，数组中的数字大小，既是石头的重量，也是石头的价值。
2.确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
3.dp数组如何初始化
dp[0] = 0;
题干提示中给出1 <= stones.length <= 30，1 <= stones[i] <= 1000，所以背包最大重量为30 * 1000 。
我们要求的target = 最大重量sum / 2，所以dp数组开到15000大小就可以了， 即dp[1501] = 0。
初始化不需要写0，因为Java默认数组初始化为0。
4.确定遍历顺序
第一层for循环遍历每个石头的重量（价值），第二层for循环遍历背包，从大往小倒序遍历==》确保每个石头只放一次。
5.举例推导dp数组
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum = 0;
for (int stone : stones) {
sum += stone;
}
int target = sum / 2;
int[] dp = new int[target + 1];
for (int i = 0; i < stones.length; i++) {
for (int j = target; j >= stones[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
}494. 目标和
sum表示集合总和，target是目标值，left表示正数+集合，right表示负数-集合。
left + right = sum
left - right = target ==> left - (sum - left) = target ==> left = (target + sum) / 2
所以问题变为，给定一个背包，容量为left，问有多少种方式能够把这个背包装满。
1.确定dp数组以及下标的含义
dp[j]表示装满背包容量为j的背包，有dp[j]种方法
2.确定递推公式
例如：dp[j]，j 为5，
- 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包
- 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包
- 已经有一个3（nums[i]） 的话，有 dp[2]种方法 凑成 容量为5的背包
- 已经有一个4（nums[i]） 的话，有 dp[1]种方法 凑成 容量为5的背包
- 已经有一个5 （nums[i]）的话，有 dp[0]种方法 凑成 容量为5的背包
那么凑整dp[5]有多少方法呢，也就是把所有的 dp[j - nums[i]] 累加起来。
3.dp数组如何初始化
dp[0] = 1;代入具体情形进行判断初始化数值
4.确定遍历顺序
0-1背包问题，右边的值由左边确定，每个物品只能放一次，第一层顺序遍历物品，第二层倒序遍历背包。
5.举例推导dp数组
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for (int num : nums) {
sum += num;
}
//如果target过大 sum将无法满足，题干说明是非负整数数组sum一定>0
if (sum < Math.abs(target)) {
return 0;
}
//正数集合容量如果不能整除则表明没有解决方案
if ((target + sum) % 2 != 0) {
return 0;
}
int left = (sum + target) / 2;
int[] dp = new int[left + 1];
dp[0] = 1;
for (int i = 0; i < nums.length; i++) {
for (int j = left; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[left];
}
}474.一和零
1.确定dp数组以及下标的含义
三个变量：m,n,最多有多少个物品，需要定义二维数组。
dp[i][j]：具有最多i个0，j个1容量的背包，最大能够装dp[i][j]个物品，最终结果返回dp[m][n]
2.确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题：dp[i][j] = max(dp[i][j], dp[i - x][j - y] + 1);
其中，m,n相当于背包的最大容量，每个物品的重量为x个0，y个1，后面+1相当于加上了这个物品的价值，也就是1组包含x个0和y个1的数字。
3.dp数组如何初始化
dp[0][0] = 0; 其他非零下标也初始化为0，便于后续取最大值max。
4.确定遍历顺序
第一层遍历物品（此处为数组中一个一个的字符串），接着遍历字符串的每个字符，统计出字符串中0和1的个数；
注意：每次循环遍历计数之后，需要再次清零，重新遍历。即初始化变量zeroNum = 0;oneNum = 0;需要写在循环里。
第二层倒序遍历背包，背包容量为m个0，n个1，两个维度，两个for循环。
5.举例推导dp数组
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
int zeroNum, oneNum;
for (String str : strs) {
zeroNum = 0;
oneNum = 0;
for (char ch : str.toCharArray()) {
if (ch == '0') {
zeroNum++;
} else {
oneNum++;
}
}
for (int i = m; i >= zeroNum; i--) {
for (int j = n; j >= oneNum; j--) {
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
}
