[动态规划]-打家劫舍

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

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

解释:这道题不是简单地隔一家偷一家这么简单,要用动态规划去计算最优的收益,如下面这个例子

[1,3,1,3,100]最大收益为103,就是偷了3和100

代码:(注释在代码中)

import java.lang.reflect.Array;
import java.util.Arrays;

public class Rob {
    public static int rob(int[] nums) {
        int n = nums.length;
        if (n==0) return 0;
        if (n==1) return nums[0];
        if (n==2) return Math.max(nums[1],nums[0]);
        //在此之前都没有问题,
        // 当n=3时,如[1,5,3],在我要去偷第三家时,我
        // 就要考虑到底是选择当前已经最大的收益还是把当前的放弃去拿走之前和和去偷下一家
        //就相当于我之前偷了1,看到下一家有5,那我把这一家是1的还回去,然后偷了5,然后到了第三家,看到有3,然后
        //计算了一下,如果偷之前的1然后再偷3加起来也没有5多,就不去偷了
        //再举一个栗子[1,3,1,3,100]
        //先偷了1,然后看到3,还回去1,偷了3,看到1,1+1<3,不管,看到3,偷了,看到100,计算了一下3+100>6,于是把3 还回去
        //把一百偷了,
        //pre相当于上一家,cur相当于当前最大收益,num相当于将要偷的一家
        int pre = 0;
        int cur = 0;
        for (int num : nums){
            int temp = cur;
            cur = Math.max(pre+num,cur);
            pre = temp;
            //System.out.println("pre="+pre+"cur="+cur+"num="+num);
        }
        return cur;
    }
}

打家劫舍 二
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

解释:因为不能同时偷第一家和最后一家,其他情况和第一题不变,那就稍微改一下第一题的代码,取两种情况的最大值就好

import java.lang.reflect.Array;
import java.util.Arrays;

public class Rob {
    public static int rob(int[] nums) {
        int n = nums.length;
        if (n==0) return 0;
        if (n==1) return nums[0];
        if (n==2) return Math.max(nums[1],nums[0]);
        return Math.max(rob_max(Arrays.copyOfRange(nums,0,n-1)),rob_max(Arrays.copyOfRange(nums,1,n)));
    }
    private static int rob_max(int[] nums) {
        int pre = 0;
        int cur = 0;
        for (int num : nums) {
            int temp = cur;
            cur = Math.max(pre + num, cur);
            pre = temp;
            //System.out.println("pre=" + pre + "cur=" + cur + "num=" + num);
        }
        return cur;
    }
}

打家劫舍 三
在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。
示例 1:

输入: [3,2,3,null,3,null,1]

image.png

输出: 7
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

解释:一种情况是第二层,另一种情况是第一层+第三层

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public static int rob(TreeNode root) {
        return SolutionTree(root).val;
    }
    public static TreeNode SolutionTree(TreeNode root){
        if (root == null){
            TreeNode treeNode = new TreeNode(0);
            return SolutionTree(treeNode);
        }
        if (root.left == null &&root.right == null){
            root.left = new TreeNode(0);
            root.right = new TreeNode(0);
            return root;
        }
        root.left = SolutionTree(root.left);
        root.right = SolutionTree(root.right);
        root.val = Math.max(root.left.val+root.right.val,root.val+root.left.left.val+
                root.left.right.val+root.right.left.val+root.right.right.val);
        return root;
    }
}

可以变化为打家劫舍的题:
给定一个整数数组 nums ，你可以对它进行一些操作。

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

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

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

class Solution {
    public static int deleteAndEarn(int[] nums) {
      int n = nums.length;
        if (n==0) return 0;
        if (n==1) return nums[0];

        int max1 = 0;

        for (int i=0;i<n;i++){
            max1 = Math.max(nums[i],max1);
        }

        int[] trans = new int[max1+1];
        for (int num:nums){
            trans[num-1] += num;
        }
        //System.out.println(Arrays.toString(trans));

        int cur = 0;
        int pre = 0;

        for (int num : trans){
            int temp = cur;
            cur = Math.max(pre+num,cur);
            pre = temp;
        }
        return cur;
    }
}