House Robber Leetcode Solution


Кыйынчылык деңгээли жеңил
Көп суралган Amazon алма Cisco Microsoft Oracle
Динамикалык программалоо

Маселени билдирүү

Бул көйгөйдө көчөдө үйлөр бар, ал эми үйдү тоногон адам бул үйлөрдү тоношу керек. Бирок маселе анын бир нече үйдү, башкача айтканда, бири-бирине жанаша тандап алышы мүмкүн эмес. Ар бир үйдүн акчасынын суммасын көрсөткөн терс эмес сандардын тизмесин эске алганда, биз ал ала турган акчанын максималдуу суммасын табышыбыз керек.

мисал

nums = [1,2,3,1]
4

Explanation:House Robber

1-үйдү уурдагыла (акча = 1), андан кийин 3-үйдү уурдагыла (акча = 3).
Жалпы сумманы тоной аласыз = 1 + 3 = 4.

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

Explanation:

Каракчы үй 1 (акча = 2), үй тоноо 3 (акча = 9), андан кийин 5-үй (акча = 1).
Жалпы сумманы тоной аласыз = 2 + 9 + 1 = 12.

жакындоо

Бул көйгөйдү ач көздүк менен чечүү мүмкүн эмес.
Келгиле, бир мисал алып көрөлү:
nums = [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) болот. Ошондуктан биз колдонобуз динамикалык программалоо аралык натыйжаларын жакындоо жана массивде сактоо.
Эсептөөдөн кийин, массивдеги nth (акыркы) индексинде сакталган маанини кайтарып беребиз.

ишке ашыруу

House Robber Leetcode Solution үчүн 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 Solution үчүн 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 Solution комплекстүүлүгүн талдоо

Убакыт татаалдыгы

O (n): биз бир үйдөн экинчи үйгө чейин бир цикл менен кайталап жатабыз, мында n - жалпы үйлөрдүн саны.

Космостун татаалдыгы 

O (n): биз аралык жыйынтыкты сактоо үчүн n өлчөмүндөгү массивди колдондук.