題目（鏈接）
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警，
給定一個代表每個房屋存放金額的非負整數陣列，計算你不觸動警報裝置的情況下，一夜之內能夠偷竊到的最高金額，
示例 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 <= 1000 <= nums[i] <= 400
題解
思路：
- 動態規劃
- 狀態轉移：用
f[i][2]的第一維表示第i個位置，第二維用0、1表示第i個位置是否選擇，
第i個位置有兩種情況：
（1）不選第i個位置，即f[i][0]，f[i][0]可以由f[i - 1][0]轉移而來，因為不選第i個位置，所以也可以由f[i - 1][1]轉移而來，因為當前位置不選，所以最高金額依然是上一個狀態的最高金額，即：f[i][0] = max(f[i - 1][0], f[i - 1][1])，
（2）選第i個位置，即f[i][1]，因為要選擇第i個位置，根據題意不能選擇兩個連續的位置，那么f[i][1]就不能由f[i - 1][1]轉移而來，只能由f[i - 1][0]轉移而來，因為要選擇當前位置，所以最高金額是上一個狀態的最高金額加上當前位置的金額，即：f[i][1] = f[i - 1][0] + nums[i - 1]，
code：
class Solution {
public:
int rob(vector<int>& nums) {
int N = nums.size(), INF = 0x3f3f3f3f;
int f[N + 10][2];
// 初始化虛擬節點
f[0][0] = 0, f[0][1] = -INF;
// 選或者不選第i個位置
for (int i = 1; i <= N; i ++){
f[i][0] = max(f[i - 1][0], f[i - 1][1]);
f[i][1] = f[i - 1][0] + nums[i - 1];
}
return max(f[N][0], f[N][1]);
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/506022.html
標籤：其他