LeetCode 198:House Robber

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.

//題目描述：你是一名專業強盜，計劃沿著一條街打家劫捨。每間房屋都儲存有一定數量的金錢，唯一能阻止你打劫的約束條件就是：
//由於房屋之間有安全系統相連，如果同一個晚上有兩間相鄰的房屋被闖入，它們就會自動聯絡警察，因此不可以打劫相鄰的房屋。
//給定一列非負整數，代表每間房屋的金錢數，計算出在不驚動警察的前提下一晚上最多可以打劫到的金錢數。

//解題思路：
//對於第i個房間我們的選擇是偷和不偷， 如果決定是偷 則第i-1個房間必須不偷 那麼 這一步的就是 dp[i] = nums(i-1) + dpNotTake[i -1] , 假設dp[i]表示打劫到第i間房屋時累計取得的金錢最大值.
//如果是不偷， 那麼上一步就無所謂是不是已經偷過， dp[i] = dp[i -1 ]， 因此 dp[i] =max(dpNotTake[i-1 ] + nums(i-1), dp[i-1] );  其中dpNotTake[i-1]=dp[i-2]
//利用動態規劃，狀態轉移方程：dp[i] = max(dp[i - 1], dp[i - 2] + num[i - 1])
//其中，dp[i]表示打劫到第i間房屋時累計取得的金錢最大值。

class Solution {
public:
	int rob(vector& nums) {
		int n = nums.size();
		if (n == 0) return 0;

		int* dp = new int[n + 1];
		dp[0] = 0;
		dp[1] = nums[0];

		for (int i = 2; i < n + 1; ++i){
			dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
		}
		return dp[n];
	}
};