打家劫舍
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警，
給定一個代表每個房屋存放金額的非負整數陣列，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額，
示例 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 ，
提示：
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 400
思路：
動態規劃，寫出初始狀態，列出轉移方程，回傳最后一項即可
代碼：
class Solution
{
public:
int rob(vector<int> &nums)
{
int n = nums.size();
if (n == 0)
return 0;
if (n == 1)
return nums[0];
vector<int> ans(n, 0);
ans[0] = nums[0];
ans[1] = max(nums[1], nums[0]);
for (int i = 2; i < n; i++)
{
ans[i] = max(ans[i - 1], ans[i - 2] + nums[i]);
}
return ans[n - 1];
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/38205.html
標籤：其他