算法训练（leetcode）二刷第三十一天 | 1049. 最后一块石头的重量 II、494. 目标和、*474. 一和零

1049. 最后一块石头的重量 II

leetcode题目地址

本题与416. 分割等和子集类似。依旧是01背包问题，本题尽可能将石头分为相等（相近）的两堆，然后两堆求差取绝对值既可。dp[j]表示背包容量为j时背包中物品的最大重量。

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// java
class Solution {public int lastStoneWeightII(int[] stones) {int sum = 0;for(int i=0; i<stones.length; i++){sum += stones[i];}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 Math.abs(sum-dp[target]*2);}
}

*494. 目标和

leetcode题目地址

二维数组

首先对所有数字求和得到sum。

设添加‘+’的数字和为x，则添加‘-’的数字之和为sum-x，则有：target = x - ( sum - x ).

则，x = ( target + sum ) / 2. 这样就将问题简化为求能够组合（添加‘+’）成 x 的数字和的方案数。

当上式中的除以2无法整除时，说明当前数组无法组合出target的方案，返回0.

要求组合成x的方案数，则将x作为背包容量。

dp[i][j]记录背包容量为 j 时，使用 0-i 的物品可以（恰好）装满背包的方案数。

当 j=0 时，即背包容量为0，若 0-i 中没有0，则只有1种方案就是不放物品；若 0-i 中有 k 个 0，则方案数为 2 ^ k（这里的来由是：每一个0都有2个状态，即选或不选，因此k个0就有 2 ^ k种组合） ;

当 i=0 时，即只使用第0个物品，只有 j == nums[0] 时的方案为1。

• 当访问到物品i时，若背包容量 j 可以放下当前物品 nums[i]，则当前物品有两种状态，即选或不选。
  • 选：背包需要腾出当前物品大小的空间来存放当前物品，即dp[i-1][j-nums[i]]
  • 不选：dp[i-1][j]
    则有：dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j]
• 若背包容量 j 放不下当前物品 nums[i]， 则dp[i][j] = dp[i-1][j].

时间复杂度： $O(n^2)$
空间复杂度： $O(n^2)$

// java
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i=0; i<nums.length; i++){sum += nums[i];}if(Math.abs(target)>sum) return 0;if((sum+target)%2==1) return 0;int x = (sum+target)/2;int[][] dp = new int[nums.length][x+1];if(nums[0]<=x) dp[0][nums[0]] = 1;int zeroCnt = 0;for(int i=0; i<nums.length; i++){if(nums[i] == 0){zeroCnt++;}dp[i][0] = (int)Math.pow(2, zeroCnt);}for(int i=1; i<nums.length; i++){for(int j=0; j<=x; j++){if(j>=nums[i]){dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]];}else{dp[i][j] = dp[i-1][j];}}}return dp[nums.length-1][x];}
}

滚动数组

思路同上，只是有一些小细节需要处理：

• 所有元素都只使用一次，因此遍历背包容量需要从后向前。
• 在初始化第一个元素即dp[0]时，需要注意，若nums[0]为0，则有2种方案（选或不选），反之只有一种方案（不选）。

时间复杂度： $O(n^2)$
空间复杂度： $O(n)$

// java
class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i=0; i<nums.length; i++){sum += nums[i];}if((sum+target) % 2 != 0) return 0;if(Math.abs(target) > sum) return 0;int x = (sum+target)/2;int[] dp = new int[x+1];if(x >= nums[0]) dp[nums[0]] = 1;dp[0] = (nums[0]==0) ? 2 : 1;for(int i=1; i<nums.length; i++){for(int j=x; j>=0; j--){if(j >= nums[i]){dp[j] += dp[j-nums[i]];}}}return dp[x];}
}

*474. 一和零

leetcode题目地址

本题是一个二维的01背包问题，背包容量是两个维度，这里使用的是滚动数组思想（二维），若要用普通的dp算法则需要使用三维数组。

dp[i][j] 代表至多 i 个 0，j 个 1 的子集个数。

由于是子集个数，不同于上题的方案数， 因此这里在留出当前物品空间后需要加1.
由于是滚动数组，则在更新时需要与当前值求最大值保留。

即：dp[i][j] = max(dp[i][j], dp[i-zeroCnt][j-oneCnt]+1).

时间复杂度： $O(n^3)$ -> $O(kmn)$
空间复杂度： $O(n^2)$ -> $O(mn)$

// java
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m+1][n+1];for(int k=0; k<strs.length; k++){int zeroCnt = 0, oneCnt = 0;char[] arr = strs[k].toCharArray();// 统计当前字符串中的0、1个数for(int j=0; j<arr.length; j++){if(arr[j] == '0') zeroCnt++;else oneCnt++;}// 01背包for(int i=m; i>=zeroCnt; i--){for(int j=n; j>=oneCnt; j--){dp[i][j] = Math.max(dp[i][j], dp[i-zeroCnt][j-oneCnt]+1);}}}return dp[m][n];}
}