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.

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.

---

很常见的动态规划问题。 一个小偷要偷街上的一系列屋子，但是不能偷连续的两个屋子，问最大能偷到多少钱。 设置一个二维数组dp[i][j]，i表示第i个屋子，j有两种取值，dp[i][0]表示不偷第i个屋子，到目前最多能偷多少钱；dp[i][1]表示偷第i个屋子，到目前最多能偷多少钱。
显然dp[i][0]=max(dp[i-1][0],dp[i-1][1])，不偷第i个屋子，前一个屋子可偷或不偷；dp[i][1]=dp[i-1][0]+nums[i]，偷第i个屋子，则前一个屋子不能偷。
实际实现的时候，dp长度比nums大1，因为dp[0]用来保留初始状态，所以for循环的时候，访问nums时i要减一。
完整代码如下：

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

本代码提交AC，用时0MS。

二刷。简化，只需要一维DP，代码如下：

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> dp(n, 0);
		dp[0] = nums[0];
		dp[1] = max(nums[1], nums[0]);
		for (int i = 2; i < n; ++i) {
			dp[i] = max(dp[i], dp[i - 1]); // 不偷
			dp[i] = max(dp[i], dp[i - 2] + nums[i]); // 偷
		}
		return dp[n - 1];
	}
};

本代码提交AC，用时4MS。