ដំណោះស្រាយចោរប្លន់ផ្ទះឡេឡេលេខកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ស៊ីស្កូ ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle
ការសរសេរកម្មវិធីឌីណាមិក

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះមានផ្ទះនៅតាមដងផ្លូវហើយចោរប្លន់ផ្ទះត្រូវតែប្លន់ផ្ទះទាំងនេះ។ ប៉ុន្តែបញ្ហាគឺថាគាត់មិនអាចប្លន់ផ្ទះច្រើនជាងមួយជាប់ៗគ្នាបានទេពោលគឺជាប់គ្នា។ ដោយបានផ្តល់នូវបញ្ជីនៃចំនួនគត់មិនអវិជ្ជមានដែលតំណាងឱ្យចំនួនទឹកប្រាក់នៃផ្ទះនីមួយៗយើងត្រូវរកចំនួនទឹកប្រាក់អតិបរមាដែលគាត់អាចទទួលបាន។

ឧទាហរណ៍

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

ការពន្យល់:ចោរប្លន់ផ្ទះ

ប្លន់ផ្ទះ ១ (លុយ = ១) ហើយបន្ទាប់មកប្លន់ផ្ទះ ៣ (លុយ = ៣) ។
ចំនួនសរុបដែលអ្នកអាចប្លន់ = ១ + ៣ = ៤ ។

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

ការពន្យល់:

ប្លន់ផ្ទះ ១ (លុយ = ២) ផ្ទះប្លន់ ៣ (លុយ = ៩) ហើយបន្ទាប់មកទី ៥ (លុយ = ១) ។
ចំនួនសរុបដែលអ្នកអាចប្លន់ = 2 + 9 + 1 = 12 ។

វិធីសាស្រ្ត

បញ្ហានេះមិនអាចត្រូវបានដោះស្រាយដោយវិធីលោភលន់ទេ។
តោះយើងយកឧទាហរណ៍៖
លេខ = [១.៧.៩.៥.១,៣,៤]

ប្រសិនបើយើងទៅរកធាតុអតិបរិមាក្នុងអារេ (ឧ។ ៩) យើងនឹងដកផលបូកនៅជិតរបស់វា (ឧ។ ៧ + ៥) ។ ហើយអ្វីដែលល្អបំផុតដែលយើងអាចមានគឺ ១៥ ដែលជាចំនួនសរុប

ប្រសិនបើយើងទៅរកធាតុទីតាំងលេខគូឬសេសយើងមានផលបូកបូក = ១៥ (៧ + ៥ + ៣) និងផលបូកសេស = ១៥ (១ + ៩ + ១ + ៤) ។

ចម្លើយដែលប្រសើរបំផុតសម្រាប់ឧទាហរណ៍នេះគឺ [៧ + ៥ + ៤] = ១២ ។

ដូច្នេះដើម្បីដោះស្រាយបញ្ហាប្រភេទនេះយើងត្រូវស្វែងរកជំរើសទាំងអស់ហើយជ្រើសរើសយកចំនួនអតិបរមាពីវា។ ចូរយើងបញ្ជាក់ថា៖

f (n) = ចំនួនធំបំផុតដែលអ្នកអាចប្លន់ពីផ្ទះដំបូងរហូតដល់ផ្ទះដែលមានលិបិក្រម។
អាយ = ចំនួនទឹកប្រាក់នៅឯផ្ទះសន្ទស្សន៍អ៊ីស។

នៅតាមផ្ទះនីមួយៗយើងមានជម្រើសប្លន់ឬទុកវាចោល។
ករណីទី ១ - ប្រសិនបើយើងជ្រើសរើសយកផ្ទះចុងក្រោយ៖
បន្ទាប់មកយើងមិនអាចជ្រើសរើសយកផ្ទះទី ១ (F-n) ដូចនេះ F (n) = An + f (n-1)
ករណីទី ២ - ប្រសិនបើយើងចាកចេញពីផ្ទះចុងក្រោយ៖
បន្ទាប់មកយើងនឹងទទួលបានប្រាក់ចំណេញអតិបរមារហូតដល់ផ្ទះទី ១ (F-n) = f (n-1)

ចូរយើងមើលករណីមូលដ្ឋាន។
n = 0, ច្បាស់ f (0) = A0 ។
n = 1 បន្ទាប់មក f (1) = អតិបរមា (A0, A1) ។

ដូច្នេះយើងអាចសង្ខេបរូបមន្តដូចខាងក្រោមៈ
f (n) = អតិបរមា (អាន + f (n-២), f (n-១))

នេះគឺជារូបមន្តហៅខ្លួនឯងដែលយើងអាចអនុវត្តបានតាមរយៈការហៅខ្លួនឯងតែត្រង់នេះភាពស្មុគស្មាញនៃពេលវេលាគឺ O (2 ^ n) ដូច្នេះយើងនឹងប្រើ ការសរសេរកម្មវិធីថាមវន្ត រកមើលនិងរក្សាទុកលទ្ធផលកម្រិតមធ្យមនៅក្នុងអារេ។
បន្ទាប់ពីការគណនាយើងនឹងប្រគល់តម្លៃដែលបានរក្សាទុកនៅសន្ទស្សន៍ទី (ចុងក្រោយ) នៅក្នុងអារេ។

ការអនុវត្តន៍

កម្មវិធី 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

ចាវ៉ាកម្មវិធីសម្រាប់ដំណោះស្រាយចោរប្លន់ផ្ទះឡេឡេសកូដ

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

ការវិភាគស្មុគស្មាញសម្រាប់ដំណោះស្រាយចោរប្លន់ផ្ទះឡេឡេសកូដ

ស្មុគស្មាញពេលវេលា

O (n)៖ យើងកំពុងធ្វើការពីផ្ទះទី ១ ដល់ផ្ទះទី ១ ក្នុងរង្វង់តែមួយដែល n គឺជាចំនួនផ្ទះសរុប។

ភាពស្មុគស្មាញនៃលំហ 

O (n)៖ យើងបានប្រើអារេទំហំ n ដើម្បីរក្សាទុកលទ្ធផលមធ្យម។