模版题-动态规划-打家劫舍 ( 动态规划优化的情况 )
- 版权声明：本站原创文章，于2026-05-20，由 管理员 发表。
- 转载请注明： 模版题-动态规划-打家劫舍 ( 动态规划优化的情况 ) | CodeGarden
**每间房屋2种状态: 偷 or 不偷**
**一夜内能偷取到到的最大金额 —— 暴力求解:列出每个房屋的偷取情况,取其中最大的。**
**这种枚举特征,很显然可以用动态规划优化掉。**
```python
class Solution:
# 你是一个专业的小偷，计划偷窃沿街的房屋。
# 每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
# 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
# 给定一个代表每个房屋存放金额的非负整数数组nums，计算不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
def rob(self, nums: List[int]) -> int:
# 每间房屋2种状态: 偷 or 不偷
# 一夜内能偷取到到的最大金额 —— 暴力求解:列出每个房屋的偷取情况,取其中最大的。
# 这种枚举特征,很显然可以用动态规划优化掉。
# dp[ i ][ 0 ] 表示不偷第i间房屋的最大金额
# dp[ i ][ 1 ] 表示偷取第i间房屋的最大金额
# 注意约束条件:两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
n = len( nums )
dp = [ [ 0, 0 ] for _ in range( n ) ]
dp[ 0 ][ 0 ] = 0
dp[ 0 ][ 1 ] = nums[ 0 ]
for i in range( 1, n ):
# 不偷第i间房 那么取第i-1间房的最大金额
dp[ i ][ 0 ] = max( dp[ i - 1 ][ 0 ], dp[ i - 1 ][ 1 ] )
# 偷取第i间房 那么第i-1间房 一定不能偷
dp[ i ][ 1 ] = dp[ i - 1 ][ 0 ] + nums[ i ]
return max( dp[ n - 1 ][ 0 ], dp[ n - 1 ][ 1 ])
```