[LeetCode] 198 - House Robber

문제

• 링크: https://leetcode.com/problems/house-robber
• 난이도: Medium
• 태그: 배열, 다이나믹 프로그래밍
• 결과: Time: 0 ms (100%), Space: 10.55 MB (61.02%)

풀이

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

        return d[len - 1];
    }
};

인접한 집을 털 수 없기 때문에, i칸까지 집을 털었을 때 최대 수익 = max(i-1칸 집을 털었을 때 수익, i-2칸 집과 i칸 집을 털었을 때 수익)이다.

이 포스트는 달레 스터디(1주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.