[ leetcode ] 198. House Robber

해당 문제는 n길이의 배열에서 서로 인접한 두 인덱스를 고르지 못하는 제약 조건 내에서 선택한 인덱스에 존재하는 숫자들의 가장 큰 합을 구하는 문제입니다.

Dynamic Programing의 기본적인 문제일 수 있고, 연습에 좋은 문제라고 생각되었습니다. 

i번째 index까지의 선택한 숫자들의 합중 가장 큰 값은 i-2까지의 가장 큰 값과 i번째 숫자를 더한 것과 i번째 숫자를 선택하지 않고 i-1까지의 합 중 가장 큰 값을 비교하여 큰 값으로 설정합니다.

dp[i-2] = max(dp[i-1], dp[i-2] + nums[i])로 표현될 수 있습니다.

 

#define max(a,b)((a) > (b) ? (a) : (b))

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

        int *dp = new int[len];
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            dp[i] = max(nums[i] + dp[i-2], dp[i-1]);
        }
        return dp[len-1];
    }
};