目錄

題目來源

題目描述

示例

提示

題目解析

算法源碼

題目來源

198. 打家劫舍 - 力扣（LeetCode）

題目描述

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

給定一個代表每個房屋存放金額的非負(fù)整數(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

題目解析

如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。

因此，小偷如果偷了第 i 間，那么必然不能偷第 i + 1間，可以選擇偷或不偷第 i + 2間。

上面這種后發(fā)狀態(tài)取決于前面狀態(tài)的，很容易就想到使用動態(tài)規(guī)劃來求解。

我們定義一個dp數(shù)組，dp[i] 的含義是，在?0 ~ i 間屋子中偷盜，小偷所能獲得的最大金額。

對于第 i 間屋子，小偷有兩種選擇：偷、或者不偷，如果：

• 小偷選擇偷第 i 間屋子，那么小偷可以獲得nums[i]的金額，但是必然不能再偷第 i - 1 間屋子了，而接下來，就變?yōu)榱送祷虿煌档?i - 2間屋子，即有轉(zhuǎn)移方程： dp[i] = dp[i-2] + nums[i]
• 小偷選擇不偷第 i 間屋子，那么小偷此時無法獲得第 i 間屋子的金額，接下來就變?yōu)橥祷虿煌档?i - 1間屋子，即有轉(zhuǎn)移方程： dp[i] = dp[i-1]

我們只要在上面兩個狀態(tài)中選擇最大的即可：

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

Java算法源碼

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;

        int[] dp = new int[n];
        
        dp[0] = nums[0];
        if(n == 1) return dp[0];

        dp[1] = Math.max(nums[0], nums[1]);
        if(n == 2) return dp[1];

        for(int i=2; i<n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }

        return dp[n-1];
    }
}

?

JavaScript算法源碼

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    const n = nums.length

    const dp = new Array(n).fill(0)

    dp[0] = nums[0]
    if(n == 1) return dp[0]

    dp[1] = Math.max(nums[0], nums[1])
    if(n == 2) return dp[1]

    for(let i=2; i<n; i++) {
        dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i])
    }

    return dp[n-1]
};

?

?

Python算法源碼

class Solution(object):
    def rob(self, nums):
        n = len(nums)

        dp = [0]*n

        dp[0] = nums[0]
        if n == 1:
            return dp[0]
        
        dp[1] = max(nums[0], nums[1])
        if n == 2:
            return dp[1]
        

        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        
        return dp[n-1]

文章來源地址http://www.zghlxwxcb.cn/news/detail-402814.html

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