【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.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

一条街上排列着有很多房子，我们现在要偷这条街，但有一个问题，相连的两座有一个报警系统，只要同时偷了相连的两座房子，警报就会拉响。所以不能偷连续两所房子，请求出我们能偷到的最多金额。

分析

动态规划解题，设f(i)是i天可以获得的最大收益

f(0) = nums[0]
f(1) = max(f(0), nums[1])
f(i) = max(f(i-1), f(i-2)+nums[i])

代码

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