အိမ်ဓားပြ Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ Apple Cisco သည် Microsoft က Oracle က
Dynamic Programming

ပြProbleနာဖော်ပြချက်

ဤပြproblemနာတွင်လမ်းတစ်အိမ်တွင်အိမ်များရှိပြီးအိမ်ဓားပြများသည်ထိုအိမ်များကိုလုယက်ကြသည်။ သို့သော်ပြtheနာတစ်ခုမှာသူသည်တစ်ခုနှင့်တစ်ခုကပ်လျက်နေသောတစ်အိမ်ထက်ပိုသောအဆက်မပြတ်လုယက်နိုင်ခြင်းမရှိပါ။ အိမ်တစ်ခုစီ၏ငွေပမာဏကိုကိုယ်စားပြုသည့်အနုတ်လက္ခဏာမဟုတ်သောကိန်းဂဏန်းများစာရင်းကိုဖော်ပြထားခြင်းဖြင့်သူရရှိနိုင်သောငွေပမာဏကိုရှာဖွေရမည်။

နမူနာ

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

ရှင်းလင်းချက်:အိမ်ဓားပြ

Rob house 1 (ပိုက်ဆံ = 1) ပြီးတော့အိမ် ၃ ကိုလု (3 = ပိုက်ဆံ = 3) ။
သင်လုယက်နိုင်သောစုစုပေါင်းပမာဏ = ၁ + ၃ = ၄ ။

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

ရှင်းလင်းချက်:

ရော့ခ်အိမ် ၁ (ငွေ = ၂)၊ လုယက်အိမ် ၃ (ငွေ = ၉)၊ ပြီးတော့ ၅ (ငွေ = ၁) ။
သင်လုယက်နိုင်သောစုစုပေါင်းပမာဏ = ၂ + ၉ + ၁ = ၁၂ ။

ချဉ်းကပ်နည်း

ဤပြproblemနာကိုလောဘကြီးသောချဉ်းကပ်မှုဖြင့်မဖြေရှင်းနိုင်ပါ။
ဥပမာတစ်ခုယူကြစို့။
nums = [1,7,9,5,1,3,4]

အကယ်၍ ကျွန်ုပ်တို့သည် array ထဲတွင် max element ကိုရှာလိုလျှင် (ဥပမာ - ၉) ၎င်း၏ကပ်လျက်ပေါင်းလဒ်ကိုဆိုလိုသည်။ (ဥပမာ - ၇ + ၅) ။ အကောင်းဆုံးရနိုင်တာက ၁၅ ဖြစ်တယ်။

အကယ်၍ ကျွန်ုပ်တို့သည် (သို့မဟုတ်) ထူးဆန်းသောအနေအထားကိုသွားလျှင် sum = 15 (7 + 5 + 3) နှင့် odd sum = 15 (1 + 9 + 1 + 4) ရှိသည်။

ဤဥပမာအတွက်အကောင်းဆုံးအဖြေမှာ [7 + 5 + 4] = 12 ဖြစ်သည်။

ထို့ကြောင့်ဤပြofနာကိုဖြေရှင်းရန်ကျွန်ုပ်တို့သည်ရွေးချယ်မှုများအားလုံးကိုပြန်လည်ရှာဖွေ။ ၎င်းတို့မှအများဆုံးရွေးရမည်။ အဲဒါကိုဖော်ပြပါရစေ။

f (n) = ပထမအိမ်မှ nth indexed house သို့သင်လုယက်နိုင်သောအကြီးမားဆုံးပမာဏ။
Ai = ith index အိမ်မှာငွေပမာဏ။

အိမ်တစ်ခုစီတွင်ကျွန်ုပ်တို့တွင်လုယက်ခြင်းသို့မဟုတ်စွန့်ခွာရန်ရွေးချယ်ခြင်းရှိသည်။
ကိစ္စ ၁ - နောက်ဆုံးအိမ်ကိုရွေးမယ်ဆိုရင်၊
ထို့နောက် (n-1) ကြိမ်မြောက်အိမ်ကိုရွေး။ မရပါ၊ ဤအရပ်မှ f (n) = An + f (n-2)
ကိစ္စ ၂ - နောက်ဆုံးအိမ်မှထွက်လျှင်
သို့ဖြစ်လျှင်အမြတ်အစွန်း (n-1) ကြိမ်မြောက်အိမ်မရောက်မှီတိုင်အောင်ကျွန်ုပ်တို့ဆက်လက်တည်ရှိနေမည်။ ထို့ကြောင့် f (n) = f (n-1)

အခြေခံအကြောင်းတရားများကိုကြည့်ကြစို့။
clearly = 0, ရှင်းရှင်းလင်းလင်း, f (0) = A0 ။
= = 1, ထို့နောက် f (1) = max ကို (A0, A1) ။

ထို့ကြောင့်ကျွန်ုပ်တို့သည်ပုံသေနည်းကိုအောက်ပါအတိုင်းအကျဉ်းချုပ်ဖော်ပြနိုင်သည်။
f (n) = max (An + f (n-2), f (n-1))

၎င်းသည်ရိုးရှင်းသောပြန်လည်လုပ်ဆောင်ခြင်းအားဖြင့်ကျွန်ုပ်တို့အကောင်အထည်ဖော်နိုင်သည့်ပြန်လည်ထူထောင်ရေးဖော်မြူလာတစ်ခုဖြစ်သည်။ သို့သော်ဤအချိန်၌ရှုပ်ထွေးမှုသည်အို (၂ ^ will) ဖြစ်သည်။ ဒါကြောင့်ငါတို့သုံးပါလိမ့်မယ် dynamic programming ကို ချဉ်းကပ်ခြင်းနှင့်တစ်ခုခင်းကျင်းအတွက်အလယ်အလတ်ရလဒ်များကိုသိုလှောင်။
တွက်ချက်ပြီးတဲ့နောက် nth (last) index မှာသိမ်းထားတဲ့ value ကို array ထဲမှာ return ပြန်ပေးတယ်။

အကောင်အထည်ဖော်ရေး

အိမ်ဓားပြ 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 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

အိမ်ဓားပြ Leetcode ဖြေရှင်းချက်များအတွက်ရှုပ်ထွေးခွဲခြမ်းစိတ်ဖြာ

အချိန်ရှုပ်ထွေး

အို ()) ကျနော်တို့ပထမhouseကနေ nth house တစ်ခုကို loop တစ်ခုတည်းမှာကြားမှာ။ n ကစုစုပေါင်းအိမ်အရေအတွက်။

အာကာသရှုပ်ထွေးမှု 

အို ()) အလယ်အလတ်ရလဒ်ကိုသိုလှောင်ရန်အရွယ်အစား n ခင်းကျင်းမှုကိုကျွန်ုပ်တို့အသုံးပြုခဲ့သည်။