一.題目要求

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

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

二.題目難度

中等

三.輸入樣例

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

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

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400

四.解題思路

遞歸——>記憶化搜索——>遞推——.滾動(dòng)數(shù)組空間優(yōu)化

五.代碼實(shí)現(xiàn)

記憶化搜索

class Solution {
public:
    int rob(vector<int>& nums) {

        vector<int> memo(nums.size(), -1);

        return dfs(memo, nums, nums.size() - 1);
    }

    int dfs(vector<int>& memo, vector<int>& nums, int n)
    {
        if(n < 0)
            return 0;
        
        if(memo[n] != -1) return memo[n];

        //在該房間偷
        int val1 = dfs(memo, nums, n - 2) + nums[n];
        //在該房間不偷
        int val2 = dfs(memo, nums, n - 1);
        memo[n] = max(val1, val2);
        return memo[n];
    }


};

遞推

class Solution {
public:
    int rob(vector<int>& nums) {

        vector<int> dp(nums.size());

        if(nums.size() == 1)
            return nums[0];

        dp[0] = nums[0];
        dp[1] = max (dp[0],nums[1]);
        for(int i = 2; i < nums.size(); i++) 
        {
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return *dp.rbegin();
    }
};

空間優(yōu)化

class Solution {
public:
    int rob(vector<int>& nums) {

        if(nums.size() == 1)
            return nums[0];

        int front1 = nums[0];
        int front2 = max(front1, nums[1]);
        int maxRob = front2;
        for(int i = 2; i < nums.size(); i++) 
        {
            maxRob = max(front1 + nums[i], front2);
            front1 = front2;
            front2 = maxRob;

        }
        return maxRob;
    }
};

六.題目總結(jié)

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

到了這里，關(guān)于【LeetCode熱題100】198. 打家劫舍（動(dòng)態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！