Үйді тонау туралы шешім


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Cisco Microsoft Oracle
Динамикалық бағдарламалау

Проблемалық мәлімдеме

Бұл мәселеде көшеде үйлер бар және үй тонаушы бұл үйлерді тонауға мәжбүр. Бірақ мәселе оның бірнеше үйді, яғни бір-біріне іргелес жатқан үйді дәйекті түрде тонай алмауында. Әр үйдің ақша мөлшерін көрсететін теріс емес бүтін сандардың тізімін ескере отырып, біз оның алатын ақшаның максималды мөлшерін анықтап алуымыз керек.

мысал

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]

Егер біз массивтегі max элементіне баратын болсақ (мысалы, 9), біз оның іргелес қосындысын жоғалтқан болар едік (мысалы. 7 + 5). Біздің қолымыздан келетіні - жалпы соманың 15-і.

Егер жұп немесе тақ позициялар элементтеріне баратын болсақ, онда бізде жұп = 15 (7 + 5 + 3) және тақ = 15 (1 + 9 + 1 + 4) болады.

Бұл мысал үшін оңтайлы жауап [7 + 5 + 4] = 12 болады.

Мәселен, осы типтегі мәселелерді шешу үшін біз барлық таңдауды рекурсивті түрде іздеуіміз керек және солардың ішінен максимумды таңдауымыз керек. Мұны белгілейік:

f (n) = бірінші үйден n-ші индекстелген үйге дейін тонауға болатын ең үлкен сома.
Ai = индекс үйіндегі ақша мөлшері.

Әр үйде біз оны тонауды немесе оны тастап кетуді шешеміз.
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-ші (соңғы) индексте сақталған мәнді қайтарамыз.

Іске асыру

Үйді тонаушы 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 шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (n): біз 1-ші үйден n-ші үйге бір цикл бойынша қайталаймыз, мұндағы n - жалпы үйлердің саны.

Ғарыштың күрделілігі 

O (n): біз аралық нәтижені сақтау үшін n өлшемді жиым қолдандық.