1.題目鏈接：

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

2.題目描述：

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

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

示例 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

3.解題思路：

該問題采用動態規劃解決，核心狀態轉移方程為：

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

dp[i] 表示前 i個房屋的最大偷竊金額

dp[i?1] 表示不偷第 i?間房屋時的最大收益

dp[i?2]+nums[i] 表示偷第 i?間房屋時的收益（需跳過前一間）

通過空間優化，代碼用三個變量替代完整的 DP 數組：

1. pas：存儲 dp[i?2]（前兩間的最優解）

2. pre：存儲 dp[i?1]（前一間的最優解）

3. tem：臨時保存狀態（用于更新）

我們采用了動態規劃的思路，通過不斷更新每間房屋可以偷盜的最大金額，來解決“打家劫舍”問題。首先，判斷如果沒有房屋，則返回 0；如果只有一間房屋，則返回該房屋的金額。然后，定義兩個變量 pas 和 pre，分別代表第 i-2 間房屋和第 i-1 間房屋的最大偷盜金額，并初始化這兩個變量。接著，從第三間房屋開始，逐步計算每一間房屋的最大偷盜金額。對于每間房屋，判斷偷或者不偷當前房屋，通過 pre 和 pas 來計算當前最大偷盜金額。具體來說，偷當前房屋時的金額是 pas + nums[i]（即前兩間房屋的偷盜金額之和）；不偷當前房屋時，金額是 pre。更新 pre 和 pas，直到遍歷完所有房屋。最終返回 pre，即最大偷盜金額。

4.題解代碼：

class Solution {
public:int rob(vector<int>& nums){if (nums.empty())return 0;//如果沒有房屋，則偷盜金額返回0if (nums.size() == 1)return nums[0];//如果只有一間房屋，則偷盜金額返回這間房屋的金額int pas = nums[0];//定義一個pas，代表第 i-2 間房屋的最大偷竊金額，初始化為第一間房屋的偷盜金額int pre = max(nums[0], nums[1]);//定義一個pre，代表第 i-1 間房屋的最大偷竊金額，初始化為前兩間房屋的最大值int tem = 0;//定義一個tem，作為臨時值儲存當前prefor (int i = 2; i < nums.size(); i++){tem = pre;//儲存pre的值pre = max(pre, pas + nums[i]); //選擇偷或者不偷當前房屋pas = tem;//將pas更新為之前的pre}return pre;//返回最大偷盜金額}
};

5.示例演算：

輸入數組：[2, 7, 9, 3, 1]

步驟	當前房屋(i)	nums[i]	操作	pas 值	pre 值	計算邏輯
初始	-	-	-	2	7	-
1	2	9	tem = pre pre = max(7, 2+9) pas = tem	7	11	max?(7,2+9)=11
2	3	3	tem = pre pre = max(11, 7+3) pas = tem	11	11	max?(11,7+3)=11
3	4	1	tem = pre pre = max(11, 11+1) pas = tem	11	12	max?(11,11+1)=12

6.復雜度計算：

時間復雜度：它通過一次遍歷處理每個房屋的金額，故時間復雜度是O(n)

空間復雜度：只使用了常數數量的額外變量，故空間復雜度為O(1)