Leetcode_198_House Robber

[lihe]

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.

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.

分析：由于同时从相邻的两个房屋中盗取财宝就会触发报警器，所以若选择盗取第i个房间的财宝就一定不能选择第i-1个房间的财宝，若不从第i个房间盗取财宝则相当于只考虑从前i-1个房间盗取财宝。

解题思路：

1. 确认原问题和子问题：
   • 原问题为求n个房间的最优解，子问题为求前1个房间，前2个房间...前n-1个房间的最优解。
2. 确认状态：
   • 第i个状态为前i个房间能获得的最大财宝。
3. 确认边界状态的值：
   • 前1个房间的最优解是第一个房间的财宝；
   • 前2个房间的最优解是第1、2个房间中较大财宝的；
4. 确定状态转移方程：
   • 选择第i个房间：第i个房间和前i-2个房间的最优解；
   • 不选择第i个房间：前i-1个房间的最优解；
   • 状态转移方程为：dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (i >= 3)。

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