릿코드(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);
}
};
반응형