?

步驟一、確定狀態(tài):

確定dp數(shù)組及下標(biāo)含義

dp數(shù)組和房屋數(shù)一樣大小， dp[i]表示到第i個(gè)房屋的時(shí)候， 能夠偷竊到的最 高金額

步驟二、推斷狀態(tài)方程:

對(duì)于當(dāng)前的dp[i]， 有兩個(gè)方向，取決于能不能考慮偷當(dāng)前房屋

如果能考慮偷當(dāng)前的房屋，那么前一個(gè)房屋肯定不能考慮，此時(shí)最高金 額: dp[i-2]+nums[i]

如果不能考慮偷當(dāng)前房屋， 那么一定可以考慮偷前一個(gè)房屋，此時(shí)最 高金額:dp[i-1]

所以dp[i] = max(dp[i-1], dp[i-2]+nums[i])

步驟三、規(guī)定初始條件:

初始條件:

如果我偷第一家
dp[0]=nums[0], dp[1]=nums[0]， 注意這個(gè)dp[1]沒(méi)得選 如果我不偷第一家

dp[0]=0, dp[1]=nums[1]， 注意此時(shí)dp[1]依然沒(méi)得選，千萬(wàn)不能說(shuō) max(nums[0], nums[1])，因?yàn)榇藭r(shí)又有可能考慮了第0家

步驟四、計(jì)算順序:

如果我偷第一家 此時(shí)不能考慮偷最后一家，所以遍歷的時(shí)候，只能到倒數(shù)第二家

如果我不偷第一家 此時(shí)可以考慮偷最后一家，所以遍歷的時(shí)候， 2~len(nums)

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) <= 2:return max(nums)dp_0 = [0 for _ in range(len(nums))]dp_1 = [0 for _ in range(len(nums))]# 偷第一家，不偷第二家dp_0[0] = nums[0]dp_0[1] = nums[0]for i in range(2, len(nums) - 1):dp_0[i] = max(dp_0[i-2] + nums[i], dp_0[i-1])# 不偷第一家， 可偷第二家dp_1[0] = 0dp_1[1] = nums[1]for i in range(2, len(nums)):dp_1[i] = max(dp_1[i-2] + nums[i], dp_1[i-1])return max(dp_0[-2], dp_1[-1])

總結(jié)

以上是生活随笔為你收集整理的103. Leetcode 213. 打家劫舍 II (动态规划-打家劫舍)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。