Leetcode House robber

Question

나는 리벳 코드에서 House Robber 문제 (dp 문제)를 시도했다. 사용자 GYX 중 하나의이 솔루션은 간단하고 우아하게 보입니다.

int rob(vector<int>& num) { 
    int n = num.size(); 
     if (n==0) return 0; 
     vector<int> result(n+1,0); 
     result[1] = num[0]; 
     for (int i=2;i<=n;i++){ 
      result[i] = max(result[i-1],result[i-2]+num[i-1]); 
     } 
     return result[n]; 
    } 

하지만 논리를 둘러 보지 못했습니다. 논리와 함께 이런 문제에 접근하는 방법을 알려주십시오.

Answer 1

k 세대의 금액을 house[k]에 저장한다고 가정합니다.

이제 max[k]에서 첫 번째 k 하우스 (그리고 첫 번째 k 전용)에서 얻을 수있는 최대 금액을 저장한다고 가정 해 보겠습니다.

지금 어떤 주택을 고려하지 않기 때문에 max[0]=0

이제 집에만 첫 번째 집, max[1] = 양을 고려하여 1

이제 고려 처음 2 개 주택,

max[2] = {중 하나 max[1]

은 (우리가 선택을 의미한다 약실 1) 또는 (집 2 + 현재 집보다 2 곳에 위치한 집까지 약탈 한 최대 금액)} = {max(max[1],house[2]+max[0])}

처음 3 개 주택과 유사하게, max[3]=max(max[2],house[3]+max[1])

이 추세를 살펴보면, max[k]=max(max[k-1],house[k]+max[k-2])을 공식화 할 수 있습니다. 이 값은 더 이상 주택이 없을 때까지 계산되며, 우리는이 첫 번째 n 하우스에서 약탈 될 수있는 최대 금액을 얻습니다.

DP 문제는 이전에 약간의 연습과 친숙 함이 있었을 때만 머리를 강타했습니다. 이것은 항상 도움이되었습니다.

Answer 2

기본적으로 대답은 f(n) = max(f(n-1), f(n-2) + arr[n])이며 그 이유를 묻습니다.

이 배열이 arr = [9,1,7,9] 및 f(n)이 함수라고 가정 해 봅시다. 배열은 [9] 경우

, 당신의 최대 f(0)는 arr[0] 될 것입니다. 배열이 [9,1] 경우

, 당신의 최대 f(1)는 max(arr[0], arr[1])입니다.

당신이 7을 선택하면 배열, [9,1,7], 당신은 1 때문에 f(n-2) + arr[n]을 선택하지 수 있습니다. 그러나 7을 선택하지 않으면 최대 f(2)은 f(1)과 같으며 f(n-1)입니다. 배열 [9,1,7,9]을 때

은 둘 다 1 & 7 드롭 9, 9 f(n) = max(f(n-1), f(n-2)+arr[n]) 식을 만족하는 경우,이 선택해야한다.