? ? ? ? leetcode原題鏈接：打家劫舍

題目描述

? ? ? ?你是一個專業的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。給定一個代表每個房屋存放金額的非負整數數組，計算你?不觸動警報裝置的情況下?，一夜之內能夠偷竊到的最高金額。

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

解題方法：動態規劃。

1. 問題定義：dp[k]表示nums[0...k]的最高偷竊金額；

2.?初始化：?

? ? ? ? dp[0] = nums[0];

? ? ? ?dp[1] = std::max(nums[0], nums[1]);

3. 狀態轉移方程：

? ? dp[k] = std::max(dp[k - 1], dp[k - 2] + nums[k]);

4. 結果返回： dp[n - 1]

C++代碼

#include <iostream>
#include <vector>
class Solution {
public:int rob(std::vector<int>& nums) {int n = nums.size();if (n == 1) {return nums[0];}// 1. 問題定義：dp[k]表示nums[0...k]的最高偷竊金額std::vector<int> dp(n, 0);// 2. 初始化dp[0] = nums[0];dp[1] = std::max(nums[0], nums[1]);// 3. 從小到大求解,遞歸表達式: dp[k]=std::max(dp[k-1], dp[k-2]+num[k])for (int k = 2; k < n; k++) {dp[k] = std::max(dp[k - 1], dp[k - 2] + nums[k]);}// 4. 返回結果return dp[n - 1];}
};