算法训练Day42|1049. 最后一块石头的重量 II ● 494. 目标和 ● 474.一和零

 1// 一维似乎更好理解
 2class Solution {
 3    public int lastStoneWeightII(int[] stones) {
 4        int sum = 0;
 5        for (int num : stones) {
 6            sum += num;
 7        }
 8        int target = sum / 2;
 9        int[] dp = new int[target + 1];
10        for (int i = 0; i < stones.length; i++) {
11            for (int j = target; j >= stones[i]; j--) {
12                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
13            }
14        }
15        return sum - 2 * dp[target];
16    } 
17}

 1class Solution {
 2    public int findTargetSumWays(int[] nums, int target) {
 3        int sum = 0;
 4        for (int num : nums) {
 5            sum += num;
 6        }
 7        if (target < 0 && sum < -target) return 0;
 8        if ((target + sum) % 2 != 0) return 0;
 9        int size = (target + sum) / 2;
10        if (size < 0) size = -size;
11
12        int[] dp = new int[size + 1];
13        dp[0] = 1;
14        for (int i = 0; i < nums.length; i++) {
15            for (int j = size; j >= nums[i]; j--) {
16                dp[j] += dp[j - nums[i]];
17            }
18        }
19        return dp[size];
20    }
21}

 1class Solution {
 2    public int findMaxForm(String[] strs, int m, int n) {
 3        // dp[i][j] 表示i个0 和 j个1时的最大子集数
 4        int[][] dp = new int[m + 1][n + 1];
 5        int one;
 6        int zero;
 7        // 先遍历物品
 8        for (String str : strs) {
 9            one = 0;
10            zero = 0;
11            // 得出每个字符串元素中包含的0和1的个数
12            for (char ch : str.toCharArray()) {
13                if (ch == '0') {
14                    zero++;
15                } else {
16                    one++;
17                }
18            }
19            // 倒序遍历背包，保证每个字符串元素只会被用一次
20            for (int i = m; i >= zero; i--) {
21                for (int j = n; j >= one; j--) {
22                    dp[i][j] = Math.max(dp[i][j], dp[i - zero][j - one] + 1);
23                }
24            }
25        }
26        return dp[m][n];
27    }
28}