?

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

1、確定原問(wèn)題中變化的變量個(gè)數(shù)

2、考慮最后一步:

對(duì)于第N間房屋，有兩個(gè)選項(xiàng): 偷竊第N間房屋，那么就不能偷竊第N?1間房屋，偷竊總金額為前N-2間房屋的最高總金額與第N間房屋的金額之和。 不偷竊第N間房屋，偷竊總金額為前N-1間房屋的最高總金額。

在兩個(gè)選項(xiàng)中選擇偷竊總金額較大的選項(xiàng)，該選項(xiàng)對(duì)應(yīng)的偷竊總金額即為前 N 間房屋能偷竊到的最高總金額。

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

用f[i]表示前i間房屋能偷竊到的最高總金額，那么就

有如下的狀態(tài)轉(zhuǎn)移方程: f[i]=max(f[i-2]+A[i],f[i-1])

前N-1間房屋的最高總金額

前N-2間房屋的最高總金額與第N間房屋的金額之和

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

初始條件: f[0]=A[0] 邊界情況: f[1]=max(A[0],A[1])

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

初始化f[0] 計(jì)算f[1],f[2]....f[n-1] 答案是f[n-1]，n是數(shù)組長(zhǎng)度

class Solution:def rob(self, nums: List[int]) -> int:if len(nums) == 0:return 0size = len(nums)if len(nums) == 1:return nums[0]# 初始化dp = [0] * (size)# 邊界dp[0] = nums[0]dp[1] = max(nums[0], nums[1])# 轉(zhuǎn)移方程for i in range(2, size):dp[i] = max(dp[i-2] + nums[i], dp[i-1])return dp[-1]

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專(zhuān)家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

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

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