[Leetcode] 198. House Robber 解題報告

題目：

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.

思路：

這是一道簡單的動态規劃題目。設dp[i]表示截止第i個位置可以獲得的最大搶劫錢數，則有如下兩種情況：

1）如果要搶目前家庭，則上家不能搶，是以受益為dp[i + i] = dp[i - 1] + nums[i + 1]；

2）如果不搶目前家庭，則受益同其前驅，即dp[i + 1] = dp[i]。注意dp[i]并不一定意味着一定搶劫了第i家。

是以狀态轉移方程為：dp[i + 1] = max(dp[i - 1] + nums[i + 1], dp[i])。算法的時間複雜度是O(n)，空間複雜度是O(n)。但是從狀态轉移方程來看，dp[i+1]隻和dp[i-1]以及dp[1]相關，是以可以進一步優化，将空間複雜度降低到O(1)。下面是優化後的代碼片段。

代碼：

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) {
    		return 0;
        }
    	if (nums.size() == 1) {
    		return nums[0];
    	}
    	int value0 = nums[0], value1 = max(value0, nums[1]);
    	for (size_t i = 2; i < nums.size(); ++i) {
    		int max_value = max(value0 + nums[i], value1);
    		value0 = value1;
    		value1 = max_value;
    	}
    	return value1;
    }
};