# LeetCode198 House Robber（打家劫舍）

xiaoxiao2021-03-01  13

# 题目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).   Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).   Total amount you can rob = 2 + 9 + 1 = 12.

# 解题思路

for (int j = 0; j < i - 1; j++) { rob_house_money[i] = max(rob_house_money[i], nums[i] + rob_house_money[j]); }

class Solution { public: int rob(vector<int>& nums) { //异常输出处理 if (nums.size() == 0) { return 0; } //初始化rob_house_money vector<int> rob_house_money = nums; for (int i = 2; i < nums.size(); i++){ //从第三个房子开始计算， 前面两个房子的值就是本身 for (int j = 0; j < i - 1; j++) { //i - 1 就略过了相邻的点（前一个店） rob_house_money[i] = max(rob_house_money[i], nums[i] + rob_house_money[j]); } } //返回数组的最大值 return *max_element(rob_house_money.begin(), rob_house_money.end()); } };

class Solution { public: int rob(vector<int>& nums) { if (nums.size() == 0) { return 0; } vector<int> rob_house_money = nums; //第二个房子需要取 第一个房子和第二个房子的最大值这样才能保持rob_house_money[i-2]是最优的 rob_house_money[1] = max(rob_house_money [0], rob_house_money [1]); for (int i = 2; i < nums.size(); i++){ rob_house_money[i] = max(rob_house_money[i - 1], rob_house_money[i-2] +nums[i]) ; } return *max_element(rob_house_money.begin(), rob_house_money.end()); } };