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

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.

Solution

• 使用DP來做這題。
• 在第N棟房子的時候，你有偷或不偷的決定：
  • 偷，代表你上一棟不能偷。DP[N] = DP[N - 2] + money[N]
  • 不偷，代表你上一棟可以偷。DP[N] = DP[N - 1]
  • 取較大值就是你在第N棟的最高金額。

Code

class Solution {
public:
    int rob(vector<int>& nums) {
        int s = nums.size();
        if(s == 0) return 0;
        if(s == 1) return nums[0];
        if(s == 2) return max(nums[0], nums[1]);

        vector<int> dp(s, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for(int i = 2; i < s; i++)
            dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);  
        return dp[s - 1];      
    }
};

tags: LeetCode C++