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

2023-08-13
江苏
本文字数：1439 字
阅读完需：约 5 分钟

本题转化为 01 背包模型的问题，需要一定的经验和思考。

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);    }}

复制代码

494. 目标和

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];    }}

复制代码

474. 一和零

dp[i][j]表示最多有 i 个 0 和 j 个 1 的 strs 的最大子集的元素数量。
递推公式：
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j- oneNum] + 1)

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];    }}