House Robber

[fkdl0048]

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

        int prev2 = 0;
        int prev1 = nums[0];

        for (int i = 1; i < n; i++) {
            int curr = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = curr;
        }

        return prev1;
    }
};

• 점화식 도출이 관건인 DP문제
• p[i] = max(dp[i-1], dp[i-2] + nums[i])
  • dp[i-1]: i-1 번째 집까지의 최대 수익을 의미.
  • dp[i-2] + nums[i]: 현재 집 i를 포함해서 i-2까지의 최대 수익
• 최대값 도출이기 때문에 공간도 2개만 사용하여 계산