打家劫舍python
时间: 2023-10-15 20:24:50 浏览: 45
打家劫舍是一个经典的动态规划问题。以下是一个使用Python解决该问题的示例代码:
```python
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(nums[i] + dp[i-2], dp[i-1])
return dp[-1]
# 示例输入
nums = [1, 2, 3, 1]
print(rob(nums)) # 输出:4
相关问题
力扣打家劫舍python
引中的代码是关于力扣打家劫舍问题的解决方案。这个问题是一个关于二叉树的变种,需要使用后序遍历的迭代方法来解决。代码中的函数robback实现了后序遍历,它会递归地计算每个节点的最大金额,返回两个值:不包括当前节点金额的最大金额和包括当前节点金额的最大金额。最后,函数robback会返回根节点的最大金额。在代码的最后,函数rob会调用robback函数,并返回最大金额。
参考代码如下:
```python
class Solution:
def rob(self, root: TreeNode) -> int:
def robback(node):
if not node:
return 0, 0
ladd, lnotadd = robback(node.left)
radd, rnotadd = robback(node.right)
return lnotadd + rnotadd + node.val, max(ladd, lnotadd) + max(radd, rnotadd)
add, notadd = robback(root)
return max(add, notadd)
```
打家劫舍二叉树Python
以下是一个用Python解决打家劫舍二叉树问题的示例:
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def rob(root):
def helper(node):
if not node:
return (0, 0)
left = helper(node.left)
right = helper(node.right)
# 偷当前节点的金额
rob_value = node.val + left[1] + right[1]
# 不偷当前节点的金额
not_rob_value = max(left) + max(right)
return (rob_value, not_rob_value)
return max(helper(root))
# 创建一个二叉树
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(3)
root.right.right = TreeNode(1)
# 调用函数计算最大金额
result = rob(root)
print("最大金额为:", result) # 输出:7
```