LeetCode 198. House Robber

The link : leetcode.com/problems/house-robber/submissions/

House Robber - LeetCode

전형적인 동적 프로그래밍 (Dynamic Programming = DP) 문제이다. 

유사한 문제로 백준 2579번 계단 오르기가 있다.

 

한 자리 건너뛰는 집만 털 수 있는 조건이다보니 로직 자체는 어렵지 않았다. 

다만 LeetCode 특유의 예외처리에서 몇 번의 실수를 거쳤다. (nums 벡터의 사이즈가 1일때에 대한 예외처리)

 

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