LC198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。偷窃到的最高金额 = 2 + 9 + 1 = 12 。

典型的动态规划问题，模板流程如下：

状态定义：
- 设动态规划表dp，dp[i]表示前i个房子在满足条件下的能偷窃到的最高金额；
状态定义：
- 设：前n间房子能够偷窃到的最大金额是dp[n]，前n-1间能够偷窃到的最大金额是dp[n-1]，此时向这些房子后面加一间房，价值为num;
- 由于不能抢相邻的房子，所以加入第n+1间房子之后，dp[n+1]为下列两种情况之一：
  - 没抢第n+1间房子：dp[n+1] = dp[n];
  - 抢了第n+1间房子；dp[n+1] = dp[n-1] + num;
  - 最终的状态转移方程：dp[n+1] = Math.max(dp[n], dp[n-1] + num);
状态初始：
- 前0间房子的最大窃取价值是0，dp[0] = 0;
返回值：
- 返回dp列表的最后一个元素值，即所有房间的最大窃取值；
简化空间复杂度：
- dp[n] 只与dp[n-1]与dp[n-2]有关，因此可以设置两个变量cur和pre交替记录，将空间复杂度降到O（1）；

//dp数组
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        //dp[i]表示前i个房子在满足条件下的能偷窃到的最高金额；
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) {
            //前i间房子的这个i，即对应第i间房子，对应nums[i-1];
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        return dp[n];
    }
}

//简化空间复杂度:使用pre 、 cur 两个指针。
class Solution {
    public int rob(int[] nums) {
        int pre = 0, cur = 0;
        for (int num : nums) {
            int tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

LC.213. 打家劫舍 II

alt

//在I的基础上增加了环状排列，意味着第一个房子和最后一个房子只能选择一个进行偷取，
//所以可以把环状排列房间问题约化为两个单排排列房子子问题：
//1.在不偷取最后一间房子的情况下，最大金额是p1
//2.在不偷取第一间房子的情况下，最大金额是pn
//最终比较并返回两者的最大值。
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if(n < 2) return nums[0];
        //dp[i] 表示前i间房子的最高收益
        //不偷最后一间房子：
        int p1 = 0, pn = 0;
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        p1 = dp[n-1];
        //不偷第一间
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        pn = dp[n];
        return Math.max(p1,pn);
    }
}

LC.337. 打家劫舍 III

alt

class Solution {
    //f表示，当前节点选中的情况下，子树可以获取的最大值
    //g表示，当前节点bu选中的情况下，子树可以获取的最大值
    HashMap<TreeNode, Integer> f = new HashMap<>();
    HashMap<TreeNode, Integer> g = new HashMap<>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0) , g.getOrDefault(root, 0));
    }
    void dfs(TreeNode node) {
        if (node == null)
            return;
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) 
        + g.getOrDefault(node.right, 0));
        
        g.put(node, Math.max(f.getOrDefault(node.left, 0), 
        g.getOrDefault(node.left, 0)) 
        + Math.max(f.getOrDefault(node.right, 0), 
        g.getOrDefault(node.right, 0)));
    }
}

alt

//是述实现的一个简化。
class Solution {
    public int rob(TreeNode root) {
        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }

    public int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int selected = node.val + l[1] + r[1];
        int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{selected, notSelected};
    }
}

LC740. 删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1：

输入：nums = [3,4,2] 输出：6 解释：删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。

示例 2：

输入：nums = [2,2,3,3,3,4] 输出：9 解释：删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。

提示：

1 <= nums.length <= 2 * 104

1 <= nums[i] <= 104

class Solution {
    //选了x，则x-1 & x+1均被删除，所有的x自然入选，
    //所以，利用int[] sum 统计出所有相同的数字，存入其同一个数字的和
    //转化为打家劫舍问题
    public int deleteAndEarn(int[] nums) {
        int maxValue = 0;
        for (int num : nums) {
            maxValue = Math.max(num, maxValue);
        }
        int[] sum = new int[maxValue+1];
        for (int num : nums) {
            sum[num] += num;
        }
        return rob(sum);
    }
    int rob(int[] sum) {
        int pre = 0, cur = 0;
        for (int num : sum) {
            int tmp = cur;
            cur = Math.max(pre + num, cur);
            pre = tmp;
        }
        return cur;
    }
}

先理解dp数组的方法，再用双指针简化的方法。

面试题LC300. 最长递增子序列

alt

class Solution {
    public int lengthOfLIS(int[] nums) {
        //dp[i]表示以nums[i]结尾的数，的最长递增子序列
        int ans = 0;
        int len = nums.length;
        if (len < 2) {
            return len;
        }
        int[] dp = new int[len];
        //初始化
        Arrays.fill(dp, 1);
        for (int i = 1; i < len; i++) {
            for(int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        for (int i = 0; i < len; i++) {
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

打家劫舍系列（动态规划）

LC198. 打家劫舍

LC.213. 打家劫舍 II

LC.337. 打家劫舍 III

LC740. 删除并获得点数

面试题LC300. 最长递增子序列