House Robber Leetcode 솔루션

문제 정책

이 문제에서는 거리에 집이 있고 집 강도가이 집을 털어 야합니다. 그러나 문제는 그가 연속적으로 하나 이상의 집, 즉 서로 인접한 집을 털 수 없다는 것입니다. 각 집의 금액을 나타내는 음이 아닌 정수 목록이 주어지면 그가받을 수있는 최대 금액을 알아 내야합니다.

예

nums = [1,2,3,1]

4

설명 :

집 1 (돈 = 1)을 약탈 한 다음 집 3 (돈 = 3)을 약탈합니다.
약탈 할 수있는 총 금액 = 1 + 3 = 4.

nums = [2,7,9,3,1]

12

설명 :

롭 하우스 1 (돈 = 2), 롭 하우스 3 (돈 = 9), 5 번째 (돈 = 1).
약탈 할 수있는 총 금액 = 2 + 9 + 1 = 12.

접근

이 문제는 탐욕스러운 접근으로 해결할 수 없습니다.
예를 들어 보겠습니다.
숫자 = [1,7,9,5,1,3,4]

배열의 최대 요소 (예 : 9)로 이동하면 인접한 합계 (예 : 7 + 5)를 잃게됩니다. 그리고 우리가 가질 수있는 최선은 총합으로 15입니다.

짝수 또는 홀수 위치 요소로 이동하면 짝수 합계 = 15 (7 + 5 + 3) 및 홀수 합계 = 15 (1 + 9 + 1 + 4)입니다.

이 예에 대한 최적의 답은 [7 + 5 + 4] = 12입니다.

따라서 이러한 유형의 문제를 해결하려면 모든 선택을 재귀 적으로 검색하고 최대를 선택해야합니다. 다음을 표시하겠습니다.

f (n) = 첫 번째 집에서 n 번째 색인 된 집으로 훔칠 수있는 최대 금액.
Ai = i 번째 인덱스 하우스의 금액.

각 집에서 우리는 그것을 강탈하거나 떠날 수 있습니다.
사례 1 – 마지막 집을 선택하면 :
그런 다음 (n-1) 번째 집을 선택할 수 없으므로 f (n) = An + f (n-2)
사례 2 – 마지막 집을 떠나는 경우 :
그런 다음 (n-1) 번째 집까지 최대 이익을 유지하므로 f (n) = f (n-1)

기본 사례를 살펴 보겠습니다.
n = 0, 분명히 f (0) = A0.
n = 1이면 f (1) = max (A0, A1).

따라서 공식을 다음과 같이 요약 할 수 있습니다.
f (n) = 최대 (An + f (n-2), f (n-1))

이것은 단순 재귀를 통해 구현할 수있는 재귀 공식이지만 여기서 시간 복잡도는 O (2 ^ n)입니다. 따라서 우리는 동적 프로그래밍 중간 결과에 접근하고 배열에 저장합니다.
계산 후 배열의 n 번째 (마지막) 인덱스에 저장된 값을 반환합니다.

실시

House Robber Leetcode 솔루션을위한 C ++ 프로그램

#include <bits/stdc++.h>
using namespace std;

int rob(vector<int>& nums)
{
    int n=nums.size();

    if(n==0) return 0;
    if(n==1) return nums[0];

    int a[n];

    a[0]=nums[0];
    a[1]=max(nums[0],nums[1]);

    for(int i=2;i<n;i++)
    a[i]=max(nums[i]+a[i-2], a[i-1]);

    return a[n-1];

}
int main() 
{
    vector<int> arr={1,2,3,1};
    
    cout<<rob(arr)<<endl;
    
  return 0; 
}

4

House Robber Leetcode 솔루션을위한 Java 프로그램

import java.util.*;
import java.lang.*;

class HouseRobber
{  
    public static int rob(int[] nums) {
        
        int n=nums.length;
        
        if(n==0) return 0;
        if(n==1) return nums[0];
        
        int a[]=new int[n];
       
        a[0]=nums[0];
        a[1]=Math.max(nums[0],nums[1]);
        
        for(int i=2;i<n;i++)
            a[i]=Math.max(nums[i]+a[i-2], a[i-1]);
        
        return a[n-1];
    }
    
    
    public static void main(String args[])
    {
        int arr[]={1,2,3,1};
        System.out.println(rob(arr));
    }
}

4

House Robber Leetcode 솔루션의 복잡성 분석

시간 복잡성

의 위에) : 우리는 단일 루프에서 1 집에서 n 집까지 반복합니다. 여기서 n은 총 주택 수입니다.

공간 복잡성 

의 위에) : 중간 결과를 저장하기 위해 크기 n의 배열을 사용했습니다.