✉️문제
https://leetcode.com/problems/house-robber-ii/description/
House Robber II - LeetCode
Can you solve this real interview question? House Robber II - You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first hou
leetcode.com
📝 접근
원형으로 돌기 때문에 House Robber I보다 조금 더 복잡하다. (0 ~ n - 2) 범위와 (0 ~ n - 1)범위의 최대값을 찾으면 된다.
help() 메소드말고 1차원 배열을 사용해도 되지만 공간 복잡도가 늘어난다.
🗝 문제풀이
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if(n == 0) return 0;
if(n == 1) return nums[0];
int result = help(nums, 0, n - 2);
int result2 = help(nums, 1, n - 1);
return Math.max(result, result2);
}
private int help(int[] nums, int l, int r) {
int prev1 = 0;
int prev2 = 0;
for(int i = l; i <= r; i++) {
final int dp = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = dp;
}
return prev1;
}
}