LeetCode 198. 打家劫舍
题目链接：198. 打家劫舍 - 力扣（LeetCode）
第一次打家劫舍，来个简单一些的，无非就是偷了当前这家偷不了下一家，因此dp[n]代表，偷前n家的时候所能偷到的最高金额，递推公式是dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
每道题都要考虑dp五步：
1）确定dp数组下标与值的关系：偷前n家的时候所能偷到的最高金额
2）确定递推公式：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
3）确定初始值：dp[0]为0，dp[1]为nums[0]
4）确定遍历的数：边界为2，到n
5）带入验证一下
代码：
#python 打家劫舍I 一维DP
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = nums[0]
for i in range(1, n):
if i == 1:
dp[i] = max(nums[i - 1], nums[i])
else:
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]LeetCode 213. 打家劫舍II
题目链接：213. 打家劫舍 II - 力扣（LeetCode）
第二次打家劫舍，在上次的基础上，头尾相连了，因此偷了最后一家就没法投第一家了，因此我们分类讨论，分别讨论[0,n - 1]与[1, n]两个区间的最大情况；同样的，dp[n]代表，偷前n家的时候所能偷到的最高金额，递推公式是dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
每道题都要考虑dp五步：
1）确定dp数组下标与值的关系：偷前n家的时候所能偷到的最高金额
2）确定递推公式：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
3）确定初始值：dp[0]为0，dp[1]为nums[0]
4）确定遍历的数：边界为2，到n
5）带入验证一下
代码：
#python 打家劫舍II
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: //分别总体讨论特殊情况
return 0
if n == 1:
return nums[0]
if n == 2:
return max(nums[0], nums[1])
def rob_helper(nums): //定义一个函数实现打家劫舍I的功能
n = len(nums)
dp = [0 for _ in range(n)]
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
return max(rob_helper(nums[1:]), rob_helper(nums[:-1])) //返回俩区间的最大值
LeetCode 337. 打家劫舍III
题目链接：337. 打家劫舍 III - 力扣（LeetCode）
第三次打家劫舍，这次是真牛逼了，小偷懂能发现二叉树了，程序员下岗再就业了属于是0.0
按照来想，无非就是选与不选当前节点，同时使用递归来实现DP.
每道题都要考虑dp五步：
1）确定dp数组下标与值的关系：偷前n家的时候所能偷到的最高金额
2）确定递推公式：dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
3）确定初始值：dp[0]为0，dp[1]为nums[0]
4）确定遍历的数：边界为2，到n
5）带入验证一下
代码：
#python //打家劫舍III
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
dp = self.traveral(root)
return max(dp)
def traveral(self, node):
if not node:
return 0, 0
left = self.traveral(node.left) //递归左子树
right = self.traveral(node.right) //递归右子树
val_0 = max(left[0], left[1]) + max(right[0], right[1]) //不选当前节点的情况
val_1 = node.val + left[0] + right[0] //选当前节点，赋值进去
return (val_0, val_1)
