第一题：1049. Last Stone Weight II

一维数组版本

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp数组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 - 2 * dp[target];}
}

二维数组版本（便于理解）

class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int s : stones) {sum += s;}int target = sum / 2;//初始化，dp[i][j]为可以放0-i物品，背包容量为j的情况下背包中的最大价值int[][] dp = new int[stones.length][target + 1];//dp[i][0]默认初始化为0//dp[0][j]取决于stones[0]for (int j = stones[0]; j <= target; j++) {dp[0][j] = stones[0];}for (int i = 1; i < stones.length; i++) {for (int j = 1; j <= target; j++) {//注意是等于if (j >= stones[i]) {//不放:dp[i - 1][j] 放:dp[i - 1][j - stones[i]] + stones[i]dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);} else {dp[i][j] = dp[i - 1][j];}}}System.out.println(dp[stones.length - 1][target]);return (sum - dp[stones.length - 1][target]) - dp[stones.length - 1][target];}
}

第二题：494. Target Sum 

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int i = 0; i < nums.length; i++) sum += nums[i];//如果target的绝对值大于sum，那么是没有方案的if (Math.abs(target) > sum) return 0;//如果(target+sum)除以2的余数不为0，也是没有方案的if ((target + sum) % 2 == 1) return 0;int bagSize = (target + sum) / 2;int[] dp = new int[bagSize + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = bagSize; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[bagSize];}
}

易于理解的二维数组版本：

class Solution {public int findTargetSumWays(int[] nums, int target) {// 01背包应用之“有多少种不同的填满背包最大容量的方法“// 易于理解的二维数组解法及详细注释int sum = 0;for(int i = 0; i < nums.length; i++) {sum += nums[i];}// 注意nums[i] >= 0的题目条件，意味着sum也是所有nums[i]的绝对值之和// 这里保证了sum + target一定是大于等于零的，也就是left大于等于零（毕竟我们定义left大于right）if(sum < Math.abs(target)){return 0;}// 利用二元一次方程组将left用target和sum表示出来（替换掉right组合），详见代码随想录对此题的分析// 如果所求的left数组和为小数，则作为整数数组的nums里的任何元素自然是没有办法凑出这个小数的if((sum + target) % 2 != 0) {return 0;}int left = (sum + target) / 2;// dp[i][j]：遍历到数组第i个数时， left为j时的能装满背包的方法总数int[][] dp = new int[nums.length][left + 1];// 初始化最上行（dp[0][j])，当nums[0] == j时（注意nums[0]和j都一定是大于等于零的，因此不需要判断等于-j时的情况），有唯一一种取法可取到j，dp[0][j]此时等于1// 其他情况dp[0][j] = 0// java整数数组默认初始值为0if (nums[0] <= left) {dp[0][nums[0]] = 1;}// 初始化最左列（dp[i][0])// 当从nums数组的索引0到i的部分有n个0时（n > 0)，每个0可以取+/-，因此有2的n次方中可以取到j = 0的方案// n = 0说明当前遍历到的数组部分没有0全为正数，因此只有一种方案可以取到j = 0（就是所有数都不取）int numZeros = 0;for(int i = 0; i < nums.length; i++) {if(nums[i] == 0) {numZeros++;}dp[i][0] = (int) Math.pow(2, numZeros);}// 递推公式分析：// 当nums[i] > j时，这时候nums[i]一定不能取，所以是dp[i - 1][j]种方案数// nums[i] <= j时，num[i]可取可不取，因此方案数是dp[i - 1][j] + dp[i - 1][j - nums[i]]// 由递推公式可知，先遍历i或j都可for(int i = 1; i < nums.length; i++) {for(int j = 1; j <= left; j++) {if(nums[i] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];}}}// 打印dp数组// for(int i = 0; i < nums.length; i++) {//     for(int j = 0; j <= left; j++) {//         System.out.print(dp[i][j] + " ");//     }//     System.out.println("");// }return dp[nums.length - 1][left];}
}

第三题：474. Ones and Zeroes

class Solution {public int findMaxForm(String[] strs, int m, int n) {//dp[i][j]表示i个0和j个1时的最大子集int[][] dp = new int[m + 1][n + 1];int oneNum, zeroNum;for (String str : strs) {oneNum = 0;zeroNum = 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];}
}