03.动态规划

[conchincradle]

0-1背包问题

Arrays.stream(array).sum();

[conchincradle]

1049. Last Stone Weight II

Constraints: 1 <= stones.length <= 30 1 <= stones[i] <= 100 Return the smallest possible weight of the left stone Input: stones = [2,7,4,1,8,1] Output: 1 背包问题就需要dp[totalWeight+1] 因此如果weight太大就不合适

[conchincradle]

answer

        int sum = Arrays.stream(stones).sum();
        int target = sum/2;
        int[] dp =  new int[target+1];
        for(int stone: stones){
            for(int i=target; i>=stone;i--){
                dp[i] = Math.max(dp[i],dp[i-stone]+stone);
            }
        }
        return sum-2*dp[target];

[conchincradle]

核心就是逆序的求转移方程 max(dp[i], dp[i-stone]+stone) 这样最大的背包每次都求减去这个石头的剩下的容量的背包的最大值是多少 这样逆序完所有的石头，不断更新

[conchincradle]

801. Minimum Swaps To Make Sequences Increasing

Return the minimum number of needed operations to make nums1 and nums2 strictly increasing. Input: nums1 = [1,3,5,4], nums2 = [1,2,3,7] Output: 1 Constraints:

2 <= nums1.length <= 105 nums2.length == nums1.length 0 <= nums1[i], nums2[i] <= 2 * 105

[conchincradle]

 public int minSwap(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int dp0 =0, dp1=1;
        for(int i=1;i<n;i++){
            int prev0=dp0,prev1=dp1;
            dp1 =n;
            dp0=n;
            if(nums1[i]>nums1[i-1]&&nums2[i]>nums2[i-1]){
                dp0 = Math.min(dp0,prev0);
                dp1=Math.min(dp1,prev1+1);
            }
            if(nums1[i]>nums2[i-1]&&nums2[i]>nums1[i-1]){
                dp0=Math.min(dp0,prev1);
                dp1=Math.min(dp1,prev0+1);
            }
        }
        return Math.min(dp0,dp1);

    }

[conchincradle]

转移方程- 因为是有答案意味着至少存在一种满足一下的情况

1. a[i]>a[i-1] && b[i]>b[i-1]
2. a[i]>b[i-1] && b[i]<a[i-1]

dp0 代表 当前位置不需要交换来保持严格递增，dp1 则是需要, prev0, prev1 代表之前的 满足1-> dp0 = prev0， 因为保持原来的顺序， dp1 = prev1+1，因为原来的交换了之后，现在也交换了，就可以保持 满足2-> dp0 = prev1,因为当前不交换就只有前一个交换了，dp1 = prev0+1 记得当前位置交换了得加1 满足1 && 2->dp0=Math.min(prev0, prev1), dp1 = Math.min(prev0+1，prev1+1)

比较绕得就是 合并第三个 用一个最大值n来简化 dp0 =n, dp1=n 1 -> dp0=min(dp0 (n), prev0), dp1 = min(dp1(n), prev1+1) 此时 dp0 = prev0, dp1 = prev1 + 1

2 -> dp0 = min(dp0 (n), prev1), dp1= min(dp1 (n), prev0+1) now dp0 = prev1, dp1 = prev0+1 1&&2-> dp0 = min(dp0 (prev0 ), prev1), dp1 = min(dp1 (prev1 +1 ), prev0+1) now it's dp0 = min(prev0, prev1), dp1= min(prev1+1, prev0+1)

so we can merge dp 0 = min(dp0, prev1), dp1 = min(dp1, prev0+1)

[conchincradle]

198. House Robber Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. Input: nums = [1,2,3,1] Output: 4

dp0[i+1] = Math.max(dp0[i],dp1[i]);
dp1[i+1] = dp0[i]+nums[i];

[conchincradle]

213. House Robber II Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police. Input: nums = [2,3,2] Output: 3 随便换一下就错误好多 首先是end-start+1写反 然后就是 dp0[i+1] = Math.max(dp0[i],dp1[i]); dp1[i+1] = dp0[i] + nums[i+start]; 此时遍历的变量位置需要加上start,错误在这里死都找不出来，这样面试肯定觉得你的debug有问题 所以难怪之前表现那么差，唯一的办法就是多刷题了 return Math.max(robMoney(nums,0,len-2),robMoney(nums,1,len-1));

[conchincradle]

337. House Robber III 二叉树变体 preorder-inorder-post order 后序遍历也就是后根遍历 从下往上，这样子进行动态规划 Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police. Input: root = [3,2,3,null,3,null,1] Output: 7

   Map<TreeNode,Integer> dp0 = new HashMap<>();
    Map<TreeNode,Integer> dp1 = new HashMap<>();

        dfs(root.left);
        dfs(root.right);
        int dp0Left = dp0.getOrDefault(root.left,0);
        int dp0Right = dp0.getOrDefault(root.right,0);
        int dp1Left = dp1.getOrDefault(root.left,0);
        int dp1Right = dp1.getOrDefault(root.right,0);
        dp0.put(root,Math.max(dp0Left,dp1Left)+Math.max(dp0Right,dp1Right));
        dp1.put(root,root.val+dp0Left+dp0Right);

可以用new int[]{0,0};来代替hashmap