[LeetCode][DP] House Robber 풀어보기

https://leetcode.com/problems/house-robber/description/

House Robber - LeetCode

 

가장 간단한 형태의 Dynamic Programming 문제입니다.

DP문제는 DP임을 파악하고 점화식을 세우는 것이 가장 중요하죠

 

해당 문제는 연속해서 선택할 수 없기 때문에 이전의 값을 선택했다, 선택하지 않았다 라는 2가지의 형태로 나뉩니다.

 

class Solution {
public:
    int rob(vector<int>& nums) {
        int N = nums.size();
        vector<pair<int, int>> dp(N);

        dp[0].second = nums[0];
        for (int i = 1; i < N; ++i)
        {
            dp[i].first = max(dp[i - 1].first, dp[i - 1].first);
            dp[i].second = dp[i - 1].first + nums[i];
        }

        return max(dp[N - 1].first, dp[N - 1].second);
    }
};

저는 메모리를 별개로 사용했지만 메모리를 아끼려면 prev와 cur을 번갈아가며 사용하면 되겠네요