代码随想录 Day43 - 动态规划（五）

package jjn.carl.dp;
import java.util.Scanner;
/**
 * @author Jiang Jining
 * @since 2023-08-13 16:39
 */
public class LeetCode1049 {
    public int lastStoneWeightII(int[] stones) {
        int totalWeight = 0;
        for (int stone : stones) {
            totalWeight += stone;
        }
        int target = totalWeight / 2;
        int[] dp = new int[3001];
        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 totalWeight - 2 * dp[target];
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int[] stones = new int[total];
        for (int i = 0; i < total; i++) {
            stones[i] = scanner.nextInt();
        }
        int stoneWeight = new LeetCode1049().lastStoneWeightII(stones);
        System.out.println(stoneWeight);
    }
}

package jjn.carl.dp;
/**
 * @author Jiang Jining
 * @since 2023-08-13 21:04
 */
public class LeetCode494 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.length, neg = diff / 2;
        int[][] dp = new int[n + 1][neg + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
}

package jjn.carl.dp;
/**
 * @author Jiang Jining
 * @since 2023-08-13 22:32
 */
public class LeetCode474 {
    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];
    }
}