算法作業_30(2017.6.13第十七周)

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.

解析：還是動态規劃的問題，之前考慮用二維數組來儲存，送出的時候一直報錯。後來就考慮用一個同樣大小的一維數組，先分别初始化前三個元素。由于沒有考慮數組大小小于3的情況，是以一直報空指針異常。需要對數組長度小于三的情況分别考慮。可能不是最優解法：

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