代码随想录Day43

Day 43 动态规划 part05（01背包问题part02）

今日任务

• 1049. 最后一块石头的重量 II
• 494. 目标和
• 474.一和零

代码实现

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

    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        //表示大小为i的背包中最多能装dp[i]的东西
        int[] dp = new int[sum/2 + 1];
        for (int i = 0; i < stones.length; i++) {
            for (int j = sum/2; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }

        }
        return sum - dp[dp.length - 1] - dp[dp.length - 1];
    }

494. 目标和

    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if ((target + sum)%2 == 1) return 0;
        if (target > sum) return 0;
        int targetSum = (target + sum)/2;
        int[] dp = new int[targetSum + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = targetSum; i >= nums[i]; j--) {
                dp[j]+=dp[j - nums[i]];
            }
        }
        return nums[targetSum];
    }

474.一和零

    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (String str : strs) {
            int zeroCount = 0;
            int oneCount = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') {
                    zeroCount++;
                } else if (c == '1') {
                    oneCount++;
                }
            }
            for (int j = m; j >= zeroCount; j--) {
                for (int k = n; k >= oneCount; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zeroCount][k - oneCount] + 1);
                }
            }
        }
        return dp[m][n];
    }

今日总结

1. 没什么可说的，太难了，基本上是凭着记忆在写，希望面试能碰到原题
2. 股票今天小亏，板块轮动太快，没什么像样的主线，亦或是这就是正常的节奏？早上强的下午就回落，下午就不一定拉哪一个，乱七八糟什么都可能涨，什么叫顺周期？