House Robber II Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 이베이 구글 Microsoft 월마트 연구소
알고리즘 코딩 동적 프로그래밍 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 36

“House Robber II”문제에서 강도는 다른 집에서 돈을 강탈하려고합니다. 집안의 금액은 배열을 통해 표시됩니다. 다음 조건에 따라 주어진 배열에 요소를 추가하여 만들 수있는 최대 금액을 찾아야합니다.

  1. 강도는 연속 된 두 집을 강탈 할 수 없습니다. 즉, 합계에 두 개의 연속 요소를 포함 할 수 없습니다. 만약 i 번째 요소가 결과에 추가되면 (나는 + 1)일과 (i – 1)요소는 제외되어야합니다.
  2. 배열은 원형입니다. 그래서 먼저지난 요소도 서로 인접합니다.

1 5 4 2
7
4 5 6 8 3
13

접근하다(브 루트 포스)

문제는 배열에 연속적이지 않은 요소를 추가하여 생성 할 수있는 최대 합계 양을 찾아야합니다. 연속적이지 않은 요소를 포함하는 모든 시퀀스 조합을 확인하기 위해 Brute force를 실행할 수 있습니다. 하지만 지수 1stN 번째 실제로 인접 해 있습니다. 따라서 결과에 둘 다 포함하지 않도록해야합니다. 직관적으로 우리는 부분 배열에서 최대 합을 찾을 수 있습니다.[1, N – 1] 및 하위 배열[2, N] 갈라져. 이제 두 하위 배열은 모두 선형입니다. 결과는 두 부분 배열 합의 최대 값이됩니다.

이제 일반적인 선형 배열의 문제를 해결해 봅시다. 배열에 원형도가없고 첫 번째 요소에서 시작하여 마지막 요소에서 끝나는 선형이라고 가정하므로 첫 번째 요소와 마지막 요소를 인접 요소로 간주하지 않습니다.

이제 다음 중 하나를 수행 할 수 있습니다.

  1. 포함 합계의 모든 요소.
  2. 제외 그 요소.

이 경우 가능한 모든 시퀀스에 의해 생성 된 합계를 찾을 수 있습니다. 비 연속 요소. 가능한 모든 조합을 찾으려면 다음을 사용할 수 있습니다. 재귀 및 역 추적. 모든 재귀 호출에서 결과 합계에 요소를 포함하거나 제외합니다. 이를 바탕으로 색인에서 요소를 선택하면 I, 다음 색인은 나는 + 2, 나는 + 3.…. 마지막 요소까지. 마찬가지로 인덱스에서 요소를 제외하면 I, 인덱스에 대한 다음 재귀를 호출 할 수 있습니다. 나는 + 1, 그것에서 비롯된 모든 가능성을 확인합니다. 이러한 방식으로 모든 요소를 ​​포함 및 제외 할 가능성을 확인합니다. 또한 합계를 구성하는 모든 요소는 비 연속 모든 대체 인덱스로 이동합니다.

암호알고리즘

  1. 배열이 비어 있으면 0;
  2. 배열에 하나의 요소가있는 경우
    • 배열을 두 부분으로 분할 할 수 없습니다. 따라서 배열의 유일한 요소를 반환하십시오.
  3. 가능한 최대 합계를 저장하는 변수 max_sum_possible을 유지합니다.
  4. 재귀 함수 호출 조합 () 하위 배열 [1, N – 1] 및 [2, N]의 모든 하위 시퀀스를 확인합니다.
    • 조합 ()  모든 하위 시퀀스의 합계를 다음과 같이 저장하는 매개 변수가 있습니다. cur_sum
    • 배열의 경우 마지막 요소를 교차하면 반환.
    • 이제 우리가 만들 수있는 모든 가능성을 확인합시다. ...을 포함하여 현재 인덱스 값
      • 현재 색인 값 추가 cur_sum
      • 이 인덱스에서 연속적이지 않은 모든 요소로 이동할 수 있도록 대체 인덱스에서 시작하는 루프를 실행합니다.
      • 더 자세한 문의 사항이 있으시거나, 견적을 원하시면 오늘 바로 연락주세요 조합 () 이 지수에
    • 현재 요소가 포함되지 않았을 때 가능성을 확인 해보자
      • cur_sum에서 현재 인덱스 값을 뺍니다. 여기서는 같은 코스를 따라 되돌아오다 우리의 솔루션
      • 더 자세한 문의 사항이 있으시거나, 견적을 원하시면 오늘 바로 연락주세요 조합 () 현재 색인을 제외 했으므로 다음 색인에서
    • 모든 단계에서 cur_sum> max_sum_possible인지 확인하고 업데이트합니다.
  5. 결과 인쇄

House Robber II 해결을위한 알고리즘 구현

C ++ 프로그램

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

void combinations(vector <int> &a , int &cur_sum , int idx , int &end , int &max_sum_possible)
{
    if(idx > end)
        return;


    cur_sum += a[idx];
    if(cur_sum > max_sum_possible)
        max_sum_possible = cur_sum;

    for(int i = idx + 2 ; i <= end ; i++)
        combinations(a , cur_sum , i , end , max_sum_possible);

    cur_sum -= a[idx];
    combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
    return;
}


int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    int max_sum_possible = 0 , cur_sum = 0 , end = n - 2;
    combinations(a , cur_sum , 0 , end , max_sum_possible);
    end++;
    combinations(a , cur_sum , 1 , end , max_sum_possible);

    return max_sum_possible;
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

자바 프로그램

import java.lang.Math;


class MutableInt
{
    public int val;
    MutableInt(int x)
    {
        this.val = x;
    }
}


class House_Robber_II
{
    static void combinations(int[] a , int cur_sum , int idx , int end , MutableInt max_sum_possible)
    {
        if(idx > end)
            return;

        cur_sum += a[idx];
        if(cur_sum > max_sum_possible.val)
            max_sum_possible.val = cur_sum;

        for(int i = idx + 2 ; i <= end ; i++)
            combinations(a , cur_sum , i , end , max_sum_possible);

        cur_sum -= a[idx];
        combinations(a , cur_sum , idx + 1 , end , max_sum_possible);
        return;
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        int cur_sum = 0 , end = n - 2;
        MutableInt max_sum_possible = new MutableInt(0);
        combinations(a , cur_sum , 0 , end , max_sum_possible);
        end++;
        combinations(a , cur_sum , 1 , end , max_sum_possible);

        return max_sum_possible.val;
    }
    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

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

시간 복잡성

O(N.2 ^ N) 비 연속 요소를 포함하는 가능한 모든 하위 시퀀스를 생성합니다.

공간 복잡성

의 위에) 재귀 스택 프레임으로 인해

접근하다(동적 프로그래밍)

이전 접근 방식에서 특정 인덱스에서

  • 포함 합계의 요소입니다.
  • 제외 요소.

House Robber II Leetcode 솔루션

취하다 ans [i, N] 범위에서 얻을 수있는 최대 합계입니다. iN. 이 결과는 ans [i + 2, N] 및 ans [i + 1, N]에 따라 달라집니다. 우리는 모든 범위를 상태 모든 상태가 하위 상태에 더 의존하도록합니다. 다른 부모 상태 문제를 해결하기 위해 특정 상태에 대해 반복해서 반복해서 해결해야 할 수도 있습니다. 이것은 최적의 하부 구조. 또한 크기가 N 인 배열의 경우 모든 'n'요소에서 얻을 수있는 최대 합계는 다음 두 결과의 최대 값이라는 결론을 내릴 수 있습니다.

  • (N – 1) 요소 및 N 번째 요소 포함
  • 까지 얻은 최상의 결과 (N – 1) N 번째 요소 제외

다음과 같은 테이블을 만들 수 있습니다. 표 [i] subarray [0, i]를 사용하여 얻을 수있는 최대 합계를 저장합니다. 그러나 모든 인덱스에 대해 두 가지 선택이 있습니다. 따라서 케이스에 대한 두 가지 결과를 저장해야합니다. 요소가 포함 된 경우와 제외 된 경우입니다.

암호알고리즘

  1. 배열이 비어 있으면 0을 반환합니다.
  2. 배열에 요소가 하나만있는 경우 해당 요소를 반환합니다.
  3. 함수 만들기 robLinear () 선형 배열에서 얻을 수있는 최대 합계를 반환합니다.
  4. robLinear () 다음과 같이 작동합니다.
    1. 다음과 같이 포함되고 제외 된 두 변수를 시작합니다. 0, 현재 요소를 각각 포함 및 제외하여 얻은 최대 결과를 저장합니다.
    2. 다음 반복마다 include는 현재 요소가됩니다. 제외 이전 요소의 결과
    3. 제외는 최대가됩니다 포함제외 이전 요소의 결과
  5. robLinear의 최대 값을 반환합니다.(1, N – 1) 및 robLinear(2, N)

House Robber II 해결을위한 알고리즘 구현

C ++ 프로그램

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

int robLinear(int l , int r , vector <int> &a)
{
    int inc = 0 , exc = 0 , temp;

    for(int i = l ; i <= r ; i++)
    {
        temp = max(inc , exc);
        inc = exc + a[i];
        exc = temp;
    }
    return max(inc , exc);
}

int rob(vector <int> &a)
{
    int n = a.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return a[0];
    return max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
}

int main()
{
    vector <int> a = {1 , 5 , 4 , 2};
    cout << rob(a) << '\n';
}

자바 프로그램

import java.lang.Math;

class House_Robber_II
{
    static int robLinear(int l , int r , int[] a)
    {
        int inc = 0 , exc = 0 , temp;

        for(int i = l ; i <= r ; i++)
        {
            temp = Math.max(inc , exc);
            inc = exc + a[i];
            exc = temp;
        }
        return Math.max(inc , exc);
    }

    static int rob(int[] a)
    {
        int n = a.length;
        if(n == 0)
            return 0;
        if(n == 1)
            return a[0];
        return Math.max(robLinear(0 , n - 2 , a) , robLinear(1 , n - 1 , a));
    }

    public static void main(String args[])
    {
        int[] a = {1 , 5 , 4 , 2};
        System.out.println(rob(a));
    }
}

7

House Robber II 해결의 복잡성 분석

시간 복잡성

의 위에), 배열을 2 번 횡단합니다. 그래서 우리는 선형적인 O (2N) 연산을합니다.

공간 복잡성

O (1) 변수에는 상수 공간 만 사용됩니다.

코멘트를 남겨

Translate »