[LeetCode] House Robber

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. 解題構想:ダイナミックプランニング.d[i]=max(d[i-2]+num[i], d[i-1]); この2つの状況は、最後から2番目の部屋が盗まれず、最後から2番目の部屋が盗まれた最大の金額を表しています.境界の状況に注意する.コード:

class Solution {
public:
    int rob(vector<int> &num) {
        int len=num.size();
        if(len==0){
            return 0;
        }
        if(len==1){
            return num[0];
        }
        if(len==2){
            return max(num[0], num[1]);
        }
        int* d=new int[len];
        
        d[0]=num[0];
        d[1]=max(num[0], num[1]);
        for(int i=2; i<len; i++){
            d[i]=max(d[i-2]+num[i], d[i-1]);
        }
        
        int result=d[len-1];
        delete[] d;
        return result;
    }
    
private:
    int max(int a, int b){
        return a>b?a:b;
    }
};