代码随想录算法训练营 Day 34
Published:
动态规划五部曲
- 确定dp数组以及下标的含义
- 确定递推公式
- 初始化dp数组
- 确定遍历顺序
- 举例推导dp数组
第5步随着输入不同而变化，因此在此省去
Q1. LeetCode 198
前四步：
- 使用一维的dp数组，dp[i]表示打劫到第i个房子最大的金额
- 递推公式：1. 要打劫当前房子，那么就不能打劫前面一个，因此$dp[i] = dp[i - 2] + money[i]$。2. 不打劫当前房子，那么最大金额就是上一套房子的最大金额，$dp[i] = dp[i - 1]$。因此$dp[i]=max(dp[i-2] + money[i], dp[i-1])$
- 初始化：从递推公式中，我们需要dp数组最开始两个的值，因此分别对其初始化。$dp[0] = money[0]$因为当前只能打劫一套，$dp[1] = max(money[0], money[1])$因为从两套中选择钱多的那一套
- 遍历顺序：从前向后遍历
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums)
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[-1]
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q2. LeetCode 213
因为房子排列成环形，所以第一个和最后一个不能同时打劫。因此分两种情况讨论：1. 不考虑最后一套，前面的房子还是和Q1一样的思路；2. 不考虑第一套，后面的房子还是和Q1一样的思路
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums)
# 不考虑最后一套房子
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n - 1):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
# 不考虑第一套房子
dp1 = [0] * n
dp1[1] = nums[1]
dp1[2] = max(nums[1], nums[2])
for i in range(3, n):
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i])
return max(dp[-2], dp1[-1])
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($n$)
Q3. LeetCode 337
树形动态规划再理解
class Solution:
def rob(self, root: Optional[TreeNode]) -> int:
dp = self.traverse(root)
return max(dp)
def traverse(self, node):
if not node:
return (0, 0)
left = self.traverse(node.left)
right = self.traverse(node.right)
not_rob_val = max(left[0], left[1]) + max(right[0], right[1])
rob_val = node.val + left[0] + right[0]
return (not_rob_val, rob_val)
复杂度分析
时间复杂度：O($n$) 空间复杂度：O($logn$)