House Robber Leetcode լուծում  


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon խնձոր Cisco Microsoft Պատգամախոս
ալգորիթմները կոդավորում Դինամիկ ծրագրավորում հարցազրույց հարցազրույցի պատրաստում LeetCode LeetCodeSolutions

Խնդիրի հայտարարություն  

Այս խնդրի մեջ փողոցում կան տներ, և տան կողոպտիչը ստիպված է թալանել այդ տները: Բայց խնդիրն այն է, որ նա չի կարող կողոպտել մեկից ավելի տներ, այսինքն `միմյանց հարակից: Հաշվի առնելով յուրաքանչյուր տան փողի չափը ներկայացնող ոչ-բացասական ամբողջ թվերի ցուցակը, մենք պետք է պարզենք, թե որքան գումար կարող է նա ստանալ:

Օրինակ

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) = Ամենամեծ գումարը, որը կարող եք թալանել առաջին տնից դեպի իններորդ ինդեքսավորված տուն:
Ai = Ith ինդեքս տան փողի գումարը:

Տես նաեւ,
Flրհեղեղի լրացման LeetCode

Յուրաքանչյուր տանը մենք ընտրում ենք այն թալանել կամ լքել այն:
դեպք 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) = առավելագույն (A0, A1):

Այսպիսով, մենք կարող ենք ամփոփել բանաձևը հետևյալ կերպ.
f (n) = առավելագույն (An + f (n-2), f (n-1))

Սա ռեկուրսիվ բանաձև է, որը մենք կարող ենք իրականացնել պարզ ռեկուրսիայի միջոցով, բայց այստեղ ժամանակի բարդությունը կլինի O (2 ^ n): Հետեւաբար մենք կօգտագործենք դինամիկ ծրագրավորում մոտեցեք և պահեք միջանկյալ արդյունքները զանգվածում:
Հաշվելուց հետո մենք կվերադարձնենք զանգվածի n- րդ (վերջին) ցուցիչում պահված արժեքը:

Իրականացման  

C ++ ծրագիր House Robber Leetcode Solution- ի համար

#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

Java ծրագիրը House Robber Leetcode Solution- ի համար

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 Solution- ի համար  

Timeամանակի բարդություն

Վրա) : մենք մեկ օղակում կրկնվում ենք 1-ին տնից դեպի XNUMX-րդ տուն, որտեղ n- ն ընդհանուր տների թիվն է:

Տիեզերական բարդություն 

Վրա) : մենք օգտագործել ենք n չափի զանգված `միջանկյալ արդյունքը պահելու համար: