당신은 직업적인 강도라고 생각해 보십시오. 그리고 당신은 거리를 따라 집을 털 계획입니다. 각 집에는 일정 금액의 돈이 저장되어 있습니다. 모든 집은 원형으로 배열됩니다. 즉, 첫 번째 집은 마지막 집의 이웃입니다. 인접한 집에는 보안 시스템이 연결되어 있고 같은 밤에 인접한 두 집에 침입하면 자동으로 경찰에 연락한다는 점을 명심해야 합니다. 따라서 각 집의 금액을 나타내는 정수 목록이 있는 경우 경찰에 알리지 않고 하룻밤에 도둑질할 수 있는 최대 금액을 결정하십시오. 따라서 배열이 [1,2,3,1]이면 출력은 4가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 다음과 같이 작동하는 배열, 시작 및 끝을 취하는 solve()라는 하나의 모듈을 사용하고 있습니다. -
- ans :=nums[시작]
- 동적 프로그래밍을 위한 하나의 테이블을 생성합니다. 이름은 dp이고 크기는 숫자 크기와 같습니다.
- dp[시작] :=숫자[시작]
- for i :=시작 + 1에서 끝
- 마지막 :=dp[i – 1]
- lastToLast :=i – 2일 때 0, 그렇지 않으면 dp[i – 2]
- dp[i] :=nums[i] + lastToLast 및 last의 최대값
- ans :=dp[i] 및 ans의 최대값
- 반환
- 강탈은 아래와 같이 합니다 -
- n :=숫자 크기
- n이 0이면 0을 반환합니다.
- n =1이면 nums[0]을 반환합니다.
- solve(nums, 0, n - 2), solve(nums, 1, n - 1)의 최대값을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector <int>& nums, int start, int end){
int ans = nums[start];
vector <int> dp(nums.size());
dp[start] = nums[start];
for(int i = start + 1; i <= end; i++){
int last = dp[i - 1];
int lastToLast = i - 2 < start? 0 : dp[i - 2];
dp[i] = max(nums[i] + lastToLast, last);
ans = max(dp[i], ans);
}
return ans;
}
int rob(vector<int>& nums) {
int n = nums.size();
if(!n)return 0;
if(n == 1)return nums[0];
return max(solve(nums, 0, n - 2), solve(nums, 1, n - 1));
}
};
main(){
vector<int> v = {1,2,3,5};
Solution ob;
cout << ob.rob(v);
} 입력
[1,2,3,5]
출력
7