打家劫舍

題目鏈接

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組，計算你 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
     偷竊到的最高金額 = 1 + 3 = 4 。

示例 2：

輸入：[2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。
     偷竊到的最高金額 = 2 + 9 + 1 = 12 。

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

這道題目的本質(zhì)是求一個數(shù)組中不相鄰元素的最大和。我們可以用動態(tài)規(guī)劃的方法來解決這個問題。動態(tài)規(guī)劃的核心是找出狀態(tài)轉(zhuǎn)移方程，即如何從已知的子問題的解得到更大的子問題的解。

我們定義dp[i]表示從第0個房屋到第i個房屋能夠偷竊到的最高金額，那么我們可以得到以下狀態(tài)轉(zhuǎn)移方程：

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

這個方程的意思是，對于第i個房屋，我們有兩種選擇：要么不偷，那么最高金額就是dp[i-1]；要么偷，那么最高金額就是dp[i-2]加上當前房屋的金額nums[i]。我們?nèi)烧咧械妮^大值作為dp[i]。

由于dp[i]只和dp[i-1]和dp[i-2]有關(guān)，所以我們不需要用一個數(shù)組來存儲所有的dp值，只需要用兩個變量來記錄前兩個狀態(tài)即可。這樣可以節(jié)省空間復(fù)雜度。

根據(jù)題目的提示，我們還需要考慮數(shù)組為空或只有一個元素的情況。這些情況下，我們直接返回0或nums[0]即可。文章來源地址http://www.zghlxwxcb.cn/news/detail-473982.html

def rob(nums):
    # 如果數(shù)組為空，返回0
    if not nums:
        return 0
    # 如果數(shù)組只有一個元素，返回該元素
    if len(nums) == 1:
        return nums[0]
    # 初始化前兩個狀態(tài)
    prev = 0 # dp[-1]
    curr = nums[0] # dp[0]
    # 遍歷數(shù)組，更新狀態(tài)
    for i in range(1, len(nums)):
        # 計算當前狀態(tài)
        temp = max(curr, prev + nums[i])
        # 更新前兩個狀態(tài)
        prev = curr
        curr = temp
    # 返回最后一個狀態(tài)
    return curr

到了這里，關(guān)于每日一題之打家劫舍的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！