动态规划之打家劫舍问题

动态规划之打家劫舍问题

1.打家劫舍2.打家劫舍II3.打家劫舍III

3.1暴力解法3.2动态规划

func rob(nums []int) int {

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

}
func max(x, y int) int {

	if x > y {
		return x
	}
	return y

}

//思路
1.确定dp数组（dp table）以及下标的含义
dp[i]：考虑下标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]取最大值，即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(nums[0], nums[1])

4.确定遍历顺序

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

5.举例推导dp数组
以示例二，输入[2,7,9,3,1]为例

//时间复杂度：O(n)
空间复杂度：O(n)

func rob(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	if len(nums) == 2 {
		return max(nums[0], nums[1])
	}

	result1 := robRange(nums[:len(nums)-1])
	result2 := robRange(nums[1:])
	return max(result1, result2)
}
//下面这个函数与打家劫舍代码一模一样
func robRange(nums []int) int {

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

	return dp[len(nums)-1]

}
func max(x, y int) int {

	if x > y {
		return x
	}
	return y

}

//思路:
这道题目和打家劫舍是差不多的，唯一区别就是成环了:
如果房屋数量大于两间，就必须考虑首尾相连的问题，第一间房屋和最后一间房屋不能同时偷窃
如何才能保证第一间房屋和最后一间房屋不同时偷窃呢？
(1)如果偷窃了第一间房屋，则不能偷窃最后一间房屋，因此偷窃房屋的范围是第一间房屋到最后第二间房屋；
(2)如果偷窃了最后一间房屋，则不能偷窃第一间房屋，因此偷窃房屋的范围是第二间房屋到最后一间房屋。

// 时间复杂度O(n) 空间复杂度O(n)

//思路:
这道题目和打家劫舍与打家劫舍II也是如出一辙，只不过这个换成了树
如果对树的遍历不够熟悉的话，那本题就有难度了
对于树的话，首先就要想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。
本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。
与打家劫舍一样，关键是要讨论当前节点抢还是不抢。
如果抢了当前节点，两个孩子就不能动，如果没抢当前节点，就可以考虑抢左右孩子（注意这里说的是“考虑”）

func rob(root *TreeNode) int {
    if root  == nil{
        return 0
    }
	if root.Left == nil && root.Right == nil {
		return root.Val
	}
	 a :=root.Val
	 if root.Left  !=nil{
		 a +=rob(root.Left.Left)+rob(root.Left.Right)
	 }
	if root.Right  !=nil{
		a +=rob(root.Right.Left)+rob(root.Right.Right)
	}
	b :=rob(root.Left)+rob(root.Right)
	return  max(a,b)
	
	
}
func max(x, y int) int {
	if x>y{
		return x
	}
	return  y
	
}

当然以上代码超时了，这个递归的过程中其实是有重复计算了。

我们计算了root的四个孙子（左右孩子的孩子）为头结点的子树的情况，又计算了root的左右孩子为头结点的子树的情况，计算左右孩子的时候其实又把孙子计算了一遍。

时间复杂度：O(n^2)，这个时间复杂度不太标准，也不容易准确化，例如越往下的节点重复计算次数就越多

空间复杂度：O(log n)，算上递推系统栈的空间

func rob(root *TreeNode) int {
	res := robTree(root)
	return max(res[0], res[1])
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func robTree(cur *TreeNode) []int {
	if cur == nil {
		return []int{0, 0}
	}
	// 后序遍历
	left := robTree(cur.Left)
	right := robTree(cur.Right)

    // 考虑去偷当前的屋子
	robCur := cur.Val + left[0] + right[0]
    // 考虑不去偷当前的屋子
	notRobCur := max(left[0], left[1]) + max(right[0], right[1])

    // 注意顺序：0:不偷，1:去偷
	return []int{notRobCur, robCur}
}

这道题目算是树形dp的入门题目，因为是在树上进行状态转移，我们在讲解二叉树的时候说过递归三部曲，那么下面我以递归三部曲为框架，其中融合动规五部曲的内容来进行讲解

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

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

参数为当前节点，代码如下：

func robTree(cur *TreeNode) []int {}

其实这里的返回数组就是dp数组。

所以dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱

2.终止条件

在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回

if cur == nil {
return []int{0, 0}
}

这也相当于dp数组的初始化

3.确定遍历顺序

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

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

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

代码如下：

// 下标0：不偷，下标1：偷

left := robTree(cur.Left)
right := robTree(cur.Right)

4.确定单层递归的逻辑

如果是偷当前节点，那么左右孩子就不能偷，robCur := cur.Val + left[0] + right[0]（如果对下标含义不理解就在回顾一下dp数组的含义）

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：notRobCur := max(left[0], left[1]) + max(right[0], right[1])

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

代码如下：

5.举例推导dp数组

以示例1为例，dp数组状态如下：（注意用后序遍历推导)

**）

递归三部曲与动规五部曲分析完毕

这道题是树形DP的入门题目，通过这道题目大家应该也了解了，所谓树形DP就是在树上进行递归公式的推导。

所以树形DP也没有那么神秘！

只不过平时我们习惯了在一维数组或者二维数组上推导公式，一下子换成了树，就需要对树的遍历方式足够了解！

时间复杂度：O(n)，每个节点只遍历了一次

空间复杂度：O(log n)，算上递推系统栈的空间