ハウス強盗リートコードソリューション


難易度 簡単に
よく聞かれる Amazon (アマゾン) Apple Cisco マイクロソフト オラクル
動的計画法

問題文

この問題では、通りに家があり、家の強盗はこれらの家を奪わなければなりません。 しかし、問題は、彼が複数の家を連続して奪うことができないということです。つまり、互いに隣接している家です。 各家の金額を表す非負の整数のリストを考えると、彼が得ることができる最大金額を見つける必要があります。

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)= max(An + f(n-2)、f(n-1))

これは単純な再帰で実装できる再帰式ですが、ここでは時間計算量はO(2 ^ n)になります。 したがって、使用します 動的計画法 中間結果にアプローチして配列に格納します。
計算後、配列のn番目(最後)のインデックスに格納されている値を返します。

製品の導入

House RobberLeetcodeソリューションの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 RobberLeetcodeソリューション用の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 RobberLeetcodeソリューションの複雑さの分析

時間の複雑さ

オン) : 1番目の家からn番目の家までXNUMXつのループで反復します。ここで、nは家の総数です。

スペースの複雑さ 

オン) : サイズnの配列を使用して、中間結果を格納しました。