今天和大家分享一下動態規劃當中的打家劫舍題目，希望在大家刷題的時候提供一些思路

打家劫舍1：

題目鏈接：??198. 打家劫舍 - 力扣（LeetCode）

題目描述：

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

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

示例 1：

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

動規5部曲：

1. 確定dp數組（dp table）以及下標的含義
2. 確定遞推公式
3. dp數組如何初始化
4. 確定遍歷順序
5. 舉例推導dp數組

dp數組的含義：

當前下標所對應的下標所對應的最大可以偷竊的金錢

確定遞推公式：

根據dp數組的含義可得，我們當前的金額最大值就是上一個房間可以偷竊的最大值和當前數值和上上一個房間可以偷竊的最大數值之和

dp數組如何初始化：

考慮最簡單的情況，假如只有一間房間，當前的dp[0]就是num[0],如果只有兩間房，那么當前的dp[0]為num[0],dp[1]為max(num[0],num[1])

確認遍歷順序：

只遍歷房間

舉例推導dp數組：

房子編號: ? ? 1 ? ?2 ? ?3 ? ?4 ? ?5
金額 (nums): ? 2 ? ?7 ? ?9 ? ?3 ? ?1

動態規劃過程 (dp):
dp[0] = 2 ? ? ? ? ? ? (偷第一個房子)
dp[1] = max(2, 7) = 7 (偷第二個房子)

dp[2] = max(7, 2+9) = 11
dp[3] = max(11, 7+3) = 11
dp[4] = max(11, 11+1) = 12

最終最大金額: dp[4] = 12

假設數組為num,那么dp[0]為num[0],dp[1]為max(num[0],num[1]),通過遍歷我們的房屋，那么就可以得到dp[i]=max(dp[i-1],dp[i]+dp[i-2])

思維講解：

?詳細了解dp數組的含義，我們這里每次dp取到的都是當前房間和前面房間可以偷竊的金錢最大數，所以當前dp值就是上一個dp或者num[i]+dp[i-2]?,從而通過遍歷房間得到我們的dp

代碼：

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

打家劫舍2：

題目鏈接：?213. 打家劫舍 II - 力扣（LeetCode）

題目描述：

你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金。這個地方所有的房屋都?圍成一圈?，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警?。

給定一個代表每個房屋存放金額的非負整數數組，計算你?在不觸動警報裝置的情況下?，今晚能夠偷竊到的最高金額。

示例 2：

輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）。偷竊到的最高金額 = 1 + 3 = 4 。

?這個題目比前面的那個多了一個條件，就是房屋是一個環形的房間，那么這個題目怎么解決呢，如何進行初始化呢，選上第一個就不能選上最后一個，如何解決這個問題呢

因為這是一個環形房間，從哪里開始都一樣，我們可以將房間分為兩組，第一組就是從第一個房間到倒數第二個房間，然后第二組就是第二個房間到倒數第一個房間，然后得出這兩組所求的最大金額，返回的就是兩組當中最大金額的最大值，第幾個到第幾個的房間偷取的最大金錢數和打家劫舍1情況相同

為什么要這樣想呢？？？?

因為這里有兩種情況：

1. 不偷最后一個房子

假設我們從第一個房子開始偷，這樣就不需要考慮偷最后一個房子，因為它與第一個房子相鄰。因此，問題就簡化為一個普通的“打家劫舍”問題，即我們從第 1 個房子到第 n-1 個房子之間選擇哪些房子偷。這個問題可以通過動態規劃來解決。

2. 不偷第一個房子

假設我們從第二個房子開始偷，這樣就不需要考慮偷第一個房子，因為它與第二個房子相鄰。因此，這樣的問題就變成了從第 2 個房子到第 n 個房子之間選擇偷哪些房子。同樣可以通過動態規劃來解決。

?

?

最后通過比較11打于10所以選11，所能偷竊的最大金額為11?

代碼：

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

?后面會繼續補充的，感謝觀看