??作者簡介：碩風和煒，CSDN-Java領域新星創(chuàng)作者??，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發(fā)技術棧|面試刷題|面經(jīng)八股文|經(jīng)驗分享|好用的網(wǎng)站工具分享??????
??座右銘：人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？??????

題目鏈接

劍指 Offer II 089. 房屋偷盜
198. 打家劫舍

題目描述

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

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

示例 1：

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

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

提示：

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

求解思路&實現(xiàn)代碼&運行結果

暴力遞歸

求解思路

1. 通過讀題目的意思，我們可以大致可以確定一下的分析思路：
2. 假設我們當前來到cur位置，如果此時cur位置我們選擇不偷，那么我們繼續(xù)下一個位置的判斷。
3. 如果我們來到當前的cur位置，此時選擇偷cur位置money，那么此時我們需要加nums[cur]位置的金額，同時到cur+2位置進行判斷。
4. 那么我們最后取得最大的金額即可。

實現(xiàn)代碼

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        return process(0,n,nums);
    }

    public int process(int index,int n,int[] nums){
        if(index>=n) return 0;
        return Math.max(process(index+1,n,nums),process(index+2,n,nums)+nums[index]);
    }
}

運行結果

記憶化搜索

求解思路

1. 根據(jù)我們遞歸的分析，在遞歸的過程中會產(chǎn)生重復的子過程，所以我們想到了加一個緩存表，也就是我們的記憶化搜索。

實現(xiàn)代碼

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n+1];
        Arrays.fill(dp,-1);
        return process(0,n,nums,dp);
    }

    public int process(int index,int n,int[] nums,int[] dp){
        if(index>=n) return 0;
        if(dp[index]!=-1) return dp[index];
        return dp[index]=Math.max(process(index+1,n,nums,dp),process(index+2,n,nums,dp)+nums[index]);
    }
}

運行結果

動態(tài)規(guī)劃

求解思路

1. 接下來我們根據(jù)之前的遞歸思路以及記憶化緩存改寫動態(tài)規(guī)劃。

實現(xiàn)代碼

class Solution {
    public int rob(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n+10];
        for(int index=n-1;index>=0;index--){
            dp[index]=Math.max(dp[index+1],dp[index+2]+nums[index]);
        }
        return dp[0];
    }
}

空間優(yōu)化

class Solution {
    public int rob(int[] nums) {
        int a=0,b=0;
        for(int index=nums.length-1;index>=0;index--){
            int c=Math.max(a,b+nums[index]);
            b=a;
            a=c;
        }
        return a;
    }
}

運行結果

共勉

最后，我想送給大家一句一直激勵我的座右銘，希望可以與大家共勉！

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

到了這里，關于【LeetCode: 劍指 Offer II 089. 房屋偷盜（打家竊舍） | 暴力遞歸=＞記憶化搜索=＞動態(tài)規(guī)劃】的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！