198.打家劫舍

文章;29. 打家劫舍

题目：198. 打家劫舍

【思路】

题目的特点：相邻的房屋装有相互连通的防盗系统。

1.确认数组及其下标含义

dp[i]：考虑下标（包括i）以内的房屋，最多可以偷窃的金额为dp[i]

2.确认递推公式

决定dp[i]的因素是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i-2] + nums[i]，即：第i-1房是一定不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2]加上第i房间偷盗的钱。

如果不偷第i房间，那么dp[i] = dp[i-1]，即考虑i-1房，（注意这里是考虑，不是一定要偷i-1房）

dp[i] = max(dp[i-2] + nums[i],dp[i-1])

3.dp数组如何初始化

从递推公式dp[i] = max(dp[i-2]+nums[i],dp[i-1])可以看出，递推公式的基础就是dp[0]和dp[1]

从dp[i]的定义上来讲，dp[0]一定是nums[0]，dp[1]则是nums[0]和nums[1]的最大值：dp[1] = max(dp[0] , dp[1])

4.确定遍历顺序

dp[i] 是根据dp[i-2]和dp[i-1]推导出来的，那么一定是从前到后遍历。

5.举例推导。。

Java实现

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

Go实现

func rob(nums []int) int {
    len := len(nums)
    if len == 1 {
        return nums[0]
    }
    dp := make([]int,len+1)
    dp[0],dp[1] = nums[0],max(nums[0],nums[1])
    for i := 2 ;i<len;i++{
        dp[i] = max(dp[i-1],dp[i-2]+nums[i])
    }
    return dp[len-1]

}

213.打家劫舍II

文章：30. 打家劫舍II

题目：213. House Robber II

【思路】

本题重点：第一件屋子和最后一间屋子是紧挨的，且不能选取相邻的房屋。

本题的区别是成环。

有三种情况：

1.考虑不包括首尾元素

2.考虑包括首元素，不包括尾元素

3.考虑包含尾元素，不包含首元素

而1的情况被2.3都包括了。因此只需要通过改变选择的下标获得二三情况的值，比较后返回即可。

Java实现

Go实现

func rob(nums []int) int {
    l := len(nums)
    if l == 1{
        return nums[0]
    }
    //区间没写对
    return max(rangeFunc(nums[:l-1]),rangeFunc(nums[1:]))
}
func rangeFunc(nums []int)int{
    len := len(nums)
    if len == 1{
        return nums[0]
    }
    dp := make([]int,len)
    dp[0] = nums[0]
    dp[1] = max(nums[0],nums[1])
    for i:=2;i<len;i++{
        dp[i] = max(dp[i-1],dp[i-2]+nums[i])
    }
    return dp[len-1]
}

337.打家劫舍III

文章：31. 打家劫舍III

题目：337. 打家劫舍 III

【思路】

本题重点：遍历二叉树，相邻的二叉树不能重复选取

遍历方式：后序遍历，因为要通过递归函数的返回值来做下一步计算。

如果我们采用递归回溯，其实是对一个节点偷与不偷得到的最大金钱都没有做记录，而是需要实时计算的。

这动态规划其实是使用状态转移容器来记录状态的变化，这里可以使用一个长度为2的数组，记录当前节点偷与不偷所得到的最大金钱。

树形dp。在树上进行状态转移。

1.确定递归函数的参数和返回值。

这里我们要求一个节点偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。

dp：下标为0，不偷；下标为1，偷

所以本题dp数组就是一个长度为2的数组，递归的过程中，系统栈会保存每一层递归的参数。

2.确定终止条件

在递归过程中，如果遇到空节点，返回一个长度为2数值为0的空数组即可。

3.确定遍历顺序

首先明确的是使用后序遍历，因为要通过递归函数的返回值来做下一步计算。

通过递归左节点，得到左节点偷与不偷的金钱。

通过递归右节点，得到右节点偷与不偷的金钱。

4.确定单层递归的逻辑

如果偷当前节点，则左右孩子都不能偷，val1 = cur.val + left[0] + right[0]

如果不偷当前节点，则左右孩子可以偷，至于偷左边还是偷右边一定是要选一个最大的，val2 = max(left[0],left[1]) + max(right[0],right[1])

最后当前节点的状态就是{val2 , val1}即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        int[] res = action(root);
        return Math.max(res[0],res[1]);
    }
    public int[] action(TreeNode node){
        int[] res = new int[2];
        if(node == null)return res;
        int[]left = action(node.left);
        int[] right = action(node.right);

        res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        res[1] = node.val + left[0] + right[0];
        return res;    
    }
}

Go实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    res := action(root)
    return max(res[0],res[1])
}
func action(node *TreeNode)[]int{
    res := make([]int,2)
    if node == nil{
        return res
    }
    left := action(node.Left)
    right := action(node.Right)

    //不偷：考虑偷左还是右
    res[0] = max(left[0],left[1]) + max(right[0],right[1])
    res[1] = node.Val + left[0] + right[0]

    return res
}

【算法总结】

打家劫舍：三道题分别是数组、环形数组、二叉树的遍历。数组则是从前往后依次遍历，选取的数组下标范围不同。二叉树则是采用后序遍历，在得到返回值的基础上进行偷还是不偷的筛选，但是对于res[0]的选择还是不太理解了。