Day 41 || 1049. 最后一块石头的重量 II 、494. 目标和、474.一和零
1049. 最后一块石头的重量 II
题目链接：力扣题目链接
思路：和“416. 分割等和子集”思路一致，也就其实想知道分开的两个部分最小差距是多少，求石头质量除以二作为背包容量，最后返回值就是总数减去 两倍所装下的质量，即分来的两部分质量的差距。
494. 目标和
题目链接：力扣题目链接
思路：可与看作分割两部分一个全加一个全减，凑全加之和即可，也就是（sum+target）/2，二维数组横向是每个值，纵向是背包大小，这个需要累加每次，dp[0][0]要设定为1。j<num 就 dp[i][j]=dp[i-1][j]，否则dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num]。一维就是只要大于等于j就dp[j]+= dp[j - num]。
474.一和零
题目链接：力扣题目链接
思路：创建一个二维的dp，这个dp两个维度分别是0和1能装入的大小，dp的值就是当前0和1能装入最多的数量。
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m+1][n+1];
for(String str : strs){
int x = 0,y = 0;
for (char ch : str.toCharArray()) {
if (ch == '0') {
x++;
} else if (ch == '1') {
y++;
}
}
for(int i=m;i>=x;i--){
for(int j=n;j>=y;j--){
dp[i][j] = Math.max(dp[i][j],dp[i-x][j-y]+1);
}
}
}
return dp[m][n];
}
}时间：3h