LeetCode 198. House Robber

LeetCode 198. House Robber

Description:

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:

input: [2, 5, 4, 3, 1]
output: 8
5+3=8

---

分析：

动态规划有一种特点，想很难想，但一想出来，编程就非常的简单。然而这个“想”的过程极其困难，像是数学题又像是脑筋急转弯，我想了很久没想出来，看了discuss，恍然大悟。
首先，变量rob表示偷当前房子能够获得的money，变量notrob表示不偷当前房子能够获得的money，两者均初始化为0。
然后，进入循环，currob表示不偷前一个房子能够获得的money加上偷当前房子能够获得的money之和，更新notrob，取两者较大的一个：偷前一个房子能够获得的money和不偷前一个房子能够获得的money，更新rob为currob；
循环结束，比较rob和notrob，返回较大的一个。

看起来有点绕，我们举个例子来分析：

输入一个数组为：[2, 5, 4, 3, 1]
运行上面算法得到(五次循环分成五列)：
currob = 2|5|6|8|7
notrob = 0|2|5|6|8
rob    = 2|5|6|8|7
所以，最终返回8，为5+3。

代码如下：

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
	int rob(vector<int>& nums) {
		int rob = 0;// max money can get if rob current house
		int notrob = 0;// max money can get if not rob current house
		for (int i = 0; i < nums.size(); i++) {
			int currob = notrob + nums[i];// if rob current value, previous house must not be robbed
			notrob = max(notrob, rob);// if not rob ith house, take the max value of robbed (i-1)th house and not rob (i-1)th house
			rob = currob;
		}
		return max(rob, notrob);
	}
};
int main() {
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	Solution s;
	cout << s.rob(nums) << endl;
	return 0;
}
/*
input:
5
2 5 4 3 1

output:
8
 */