릿코드(LEETCODE)

213. House Robber II

cepiloth 2020. 2. 8. 15:20
반응형

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

 

House Robber II - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

dp 접근

0 부터 마지막 -1 까지 dp 합

1 부터 마지막까지 dp 합

두수중 가장 큰 수를 출력

class Solution {
public:
    int rob(vector<int>& nums) {
        int size = nums.size();
        if(size == 0)
            return 0;
        else if(size == 1)
            return nums[0];
        
        int best_so_far = nums[0];
        int minus_two = 0;
        
        for(int i = 1; i < size - 1; ++i) {
            int tmp = best_so_far;
            best_so_far = max(best_so_far, minus_two + nums[i]);
            minus_two = tmp;
        }
            
        int new_best_so_far = nums[1];
        minus_two = 0;
        for(int i = 2; i < size; ++i) {
            int tmp = new_best_so_far;
            new_best_so_far = max(new_best_so_far, minus_two + nums[i]);
            minus_two = tmp;
        }
        
        return max(best_so_far, new_best_so_far);
    }
};
반응형