力扣爆刷第129天之动态规划五连刷（完全平方数、单词拆分、打劫劫舍）

力扣爆刷第129天之动态规划五连刷（完全平方数、单词拆分、打劫劫舍）

一、279. 完全平方数

题目链接：https://leetcode.cn/problems/perfect-squares/description/
思路：本题和最少零钱兑换是一样的，都是完全背包求最小数量，但是求的是用的物品的最小数量，这个物品不用区分组合还是排序，只要是最小数量就可以，所以完全背包，物品和背包谁内谁外都可以，不影响，定义dp[i]表示背包为N时装满所需的最小物品数量为dp[i]。
另外谨记：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1; i*i <= n; i++) {
            for(int j = i*i; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}

二、139. 单词拆分

题目链接：https://leetcode.cn/problems/word-break/description/
思路：单词拆分中的单词可以不限数量，问能否拼接为字符串，拼接是讲究顺序的，显然是完全背包求排列数，背包在外，物品在内。
递推公式：完全背包求组合数和排列数都是一个公式 dp[i] = dp[i-nums[j]]。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for(int i = 1; i < dp.length; i++) {
            for(String t : wordDict) {
                if(t.length() > i || dp[i] || !isTrue(s, t, i-t.length(), i)) continue;
                dp[i] = dp[i-t.length()];
            }
        }
        return dp[s.length()];
    }
    
    boolean isTrue(String s, String t, int x, int y) {
        int i = 0;
        while(x < y) {
            if(s.charAt(x) != t.charAt(i)) return false;
            x++;
            i++;
        }
        return true;
    }
    
}

三、198.打家劫舍

题目链接：https://leetcode.cn/problems/house-robber/description/
思路：打家劫舍是一个经典问题，不能连续偷一家，所以对于每天有两种选择，即偷与不偷，偷的话，就依赖于前前家的结果，不偷的话，就依赖于前一天，故dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        int a = nums[0], b = Math.max(a, nums[1]), c = 0;
        for(int i = 2; i < nums.length; i++) {
            c = Math.max(b, a + nums[i]);
            a = b;
            b = c;
        }
        return b;
    }
}

四、213. 打家劫舍 II

题目链接：https://leetcode.cn/problems/house-robber-ii/description/
思路：本题是一个变形，就是可以变成了一个环形数组，需要分情况考虑首尾问题，因为不能偷相邻的两家，所以，可以直接逻辑分割成两个数组，一个包含头[0, len-1]，一个包含尾[1, len]。然后分别在两个区间上去求最大值。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        int a = getMax(nums, 0, nums.length-2);
        int b = getMax(nums, 1, nums.length-1);
        return Math.max(a, b);
    }

    int getMax(int[] nums, int left, int right) {
        int a = nums[left], b = Math.max(a, nums[left+1]), c = 0;
        for(int i = left + 2; i <= right; i++) {
            c = Math.max(b, a + nums[i]);
            a = b;
            b = c;
        }
        return b;
    }
}

五、337. 打家劫舍 III

题目链接：https://leetcode.cn/problems/house-robber-iii/description/
思路：本题又是一个变体，虽然也是大家劫舍，但是变成了树的遍历了，也是要求不能同时偷一个家，那么对于每一个节点也是有两种选择，即偷与不偷，该节点偷的话，左右子节点就不能偷，该节点不偷的话，左右子节点偷与不偷都行记录最大值就可以。所以采用后序遍历，对于动态规划来说，无法就是状态与选择，把握住这个所有的动态规划都手拿把掐。

class Solution {
    public int rob(TreeNode root) {
        int[] dp = traverse(root);
        return Math.max(dp[0], dp[1]);
    }
    
    int[] traverse(TreeNode root) {
        if(root == null) {
            return new int[2];
        }
        int[] left = traverse(root.left);
        int[] right = traverse(root.right);
        int[] dp = new int[2];
        dp[0] = root.val + left[1] + right[1];
        dp[1] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return dp;
    }
    
}