目錄

前言：

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

213. 打家劫舍 II - 力扣（LeetCode）

?總結(jié)：

前言：

我們今天繼續(xù)刷動(dòng)態(tài)規(guī)劃的題，希望大家可以和我一起堅(jiān)持下去。

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

你是一個(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)能夠偷竊到的最高金額。

?解題思路：我們要先快速確定出這道題的解題方向，我們讀題后發(fā)現(xiàn)：當(dāng)前房間偷不偷，取決于它前一個(gè)房間有沒有被偷，因此可以確定出房間之間是存在這樣一個(gè)遞推關(guān)系的，因此我們確定了動(dòng)態(tài)規(guī)劃的思路，既然是動(dòng)態(tài)規(guī)劃，我們就嚴(yán)格按照動(dòng)態(tài)規(guī)劃五步走：

1.確定dp數(shù)組的含義以及下標(biāo)的含義：dp[i]表示包含這個(gè)房間他所能偷盜的最大金幣的總和。

2.遞推公式：我們用圖片舉例，假設(shè)此時(shí)我們要判斷到最后一個(gè)房間的時(shí)候最大的金幣數(shù)

其實(shí)就兩個(gè)狀態(tài)我們分類討論：

1.偷最后一個(gè)房間：

?既然5房間決定要偷了，那么4房間一定不偷，那么此時(shí)能夠獲得到的最大金幣dp[5]其實(shí)就等于nums[5]+dp[3]。我們要理解正確理解dp數(shù)組的含義，才可以理解這個(gè)公式。

我們這里的下標(biāo)只是為了方便理解，實(shí)際上我們?cè)跇?gòu)建的時(shí)候，dp數(shù)組是從0開始的，也就是說dp[0]就是第一次房間能夠偷到的最大金幣數(shù)。

2.不偷最后一個(gè)房間：

?既然5房間不偷，那么此時(shí)能夠得到的最大金幣 dp[5 ]= dp[4],此時(shí)我們的問題就又回到了對(duì)dp[4]進(jìn)行討論，也就是對(duì)4號(hào)房間再次進(jìn)行偷與不偷的討論。

經(jīng)過這個(gè)講解，相信大家其實(shí)對(duì)打家劫舍問題的遞推思路已經(jīng)清晰：我們每一次比較這個(gè)這個(gè)房間偷與不偷所得到的金幣數(shù)量，選擇較大的作為dp數(shù)組的元素，這樣不斷遞推，最后返回最后一個(gè)房間對(duì)應(yīng)的dp數(shù)組的元素。

公式為：?dp[i]=max(nums[i]+dp[i-2],dp[i-1]);

?3.dp數(shù)組的初始化：我們根據(jù)遞推公式就可以知道只需要初始化dp[0]與dp[1]的值就好了。其實(shí)二者的初始化很好理解：
????????dp[0]:從頭開始包含第一個(gè)房間的最大金幣數(shù)，那么當(dāng)前只有一個(gè)房間，要想得到最大金幣數(shù)就必須偷這個(gè)房間，那就是dp[0]=nums[0]。

????????dp[1]:從頭開始到第二間房間的最大金幣數(shù)，因?yàn)槲覀儾荒芡迪噜彽膬蓚€(gè)房間，那么想要得到最大的金幣數(shù)，就只能偷1或者偷2，選擇最大的偷。那么就是dp[1]=max(dp[0],dp[1])。

4.遍歷順序：根據(jù)公式可得是從前往后推，遍歷順序自然也是從前往后。

經(jīng)過我們?cè)敿?xì)的分析，代碼的框架其實(shí)就已經(jīng)搭建起來了，我們要做的只剩下補(bǔ)全這個(gè)框架。

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==1)
        {
            return nums[0];
        }
        else if(nums.size()==2)
        {
            return max(nums[0],nums[1]);
        }
       vector<int>dp(nums.size());
       dp[0]=nums[0];
       dp[1]=max(nums[0],nums[1]);
       for(int i=2;i<nums.size();i++)
       {
           dp[i]=max(nums[i]+dp[i-2],dp[i-1]);
       }       
       return dp[nums.size()-1];
    }
};

213. 打家劫舍 II - 力扣（LeetCode）

你是一個(gè)專業(yè)的小偷，計(jì)劃偷竊沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個(gè)地方所有的房屋都 圍成一圈 ，這意味著第一個(gè)房屋和最后一個(gè)房屋是緊挨著的。同時(shí)，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會(huì)自動(dòng)報(bào)警 。

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

?其實(shí)這道題就是把改變了房間結(jié)構(gòu)，讓首尾相連，房間結(jié)構(gòu)從線性變?yōu)榱谁h(huán)形。

其實(shí)就是分類討論：

因?yàn)榇藭r(shí)首尾元素相連，因此我們?cè)谶x擇的時(shí)候只有兩種可能：

1.一定不偷尾。

2.一定不偷首。

?

在明確邏輯之后，代碼就非常明確了：

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

        if (nums.size() == 0) 
        {
            return 0;
        }
        if (nums.size() == 1)
        { 
            return nums[0];
        }
        int result1 = getmax(nums, 0, nums.size() - 2); //不對(duì)首進(jìn)行考慮
        int result2 = getmax(nums, 1, nums.size() - 1); //不對(duì)尾進(jìn)行考慮
        return max(result1, result2);
    }
    
    int getmax(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};    

我們對(duì)改動(dòng)做一下講解：該函數(shù)的目的是計(jì)算在[start,end]范圍內(nèi)選擇數(shù)字進(jìn)行相加得到的最大和，其中每個(gè)數(shù)字只能選擇一次。函數(shù)的實(shí)現(xiàn)過程如下：

1. 如果開始位置和結(jié)束位置相等，則直接返回?cái)?shù)組下標(biāo)為start的數(shù)字作為最大和。
2. 首先，我們定義一個(gè)大小與原始數(shù)組相同的dp數(shù)組，dp[i]表示在范圍[0,i]內(nèi)選擇數(shù)字得到的最大和。
3. 然后，我們初始化dp[0]為nums[0]，dp[1]為max(nums[0], nums[1])，因?yàn)樵诘谝缓偷诙€(gè)位置的數(shù)字中選擇最大的那個(gè)能夠確保我們得到最大和。
4. 接下來，我們從第三個(gè)位置（即start+2）開始，循環(huán)遍歷整個(gè)數(shù)組。在每個(gè)位置i處，我們有兩種選擇：

• 選擇當(dāng)前位置i的數(shù)字，這時(shí)最大和為dp[i-2]+nums[i]；
• 不選擇當(dāng)前位置i的數(shù)字，這時(shí)最大和為dp[i-1]。

5. 將兩種選擇的結(jié)果取max，更新dp[i]。
6. 最后，返回dp[end]作為[start,end]范圍內(nèi)選擇數(shù)字相加得到的最大和。

需要注意的是，該算法的時(shí)間復(fù)雜度為O(N)，其中N為數(shù)組的長度。

?總結(jié)：

? ? ? ? 打家劫舍類型題目里面給我們提供的這個(gè)算法思路真的很精彩，不愧是動(dòng)態(tài)規(guī)劃的經(jīng)典例題。

如果我的內(nèi)容對(duì)你有幫助，請(qǐng)點(diǎn)贊，評(píng)論，收藏。創(chuàng)作不易，大家的支持就是我堅(jiān)持下去的動(dòng)力！

?

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

到了這里，關(guān)于【力扣刷題 | 第十六題】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！