ပန်းချီ Algorithm ပန်းချီ


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် CodeNation Facebook က Google အလိုလိုသိတတ်သော JP Morgan မော်ဂန်စတန်လေ
အခင်းအကျင်း Dynamic Programming LeetCode

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

ပန်းချီဆွဲခြင်းအဂတိလိုက်စားမှုကသင့်အားပို့စ်အချို့ (သစ်သားအပိုင်းအစများသို့မဟုတ်အချို့အပိုင်းများ) နှင့်အရောင်အချို့ရှိသည့်ခြံစည်းရိုးတစ်ခုပေးထားသည်ဟုဖော်ပြထားသည်။ အနီးဆုံးခြံစည်းရိုး ၂ ခုတည်းသာအရောင်တူသောခြံစည်းရိုးကိုဆေးသုတ်ရန်နည်းလမ်းများစွာကိုရှာပါ။ ဒီနံပါတ်ကအကြီးကြီးဖြစ်လို့အဖြေ modulo 2 ကိုပြန်ပို့ပါ။

နမူနာ

ပန်းချီ Algorithm ပန်းချီ

Number of posts/wooden sticks = 2
Number of colors = 2
4

ရှင်းလင်းချက်
ပို့စ်နှစ်ခုလုံးကိုအရောင်နှစ်မျိုးနဲ့ပန်းချီဆွဲနိုင်ပါတယ်။ ပြီးတော့ပန်းချီကားတွေကိုအရောင်တောက်တောက်နဲ့လုပ်ဖို့နည်းလမ်း ၂ ခုရှိတယ်။ ဒီတော့စုစုပေါင်းမင်းမှာနည်းလမ်း ၄ ခုရှိတယ်။

ပန်းချီခြံစည်းရိုး Algorithm များအတွက်ချဉ်းကပ်မှု

နုံနည်းဖြင့်ချဉ်းကပ်ကြပါစို့။ ကျွန်ုပ်တို့တွင် n ပို့စ်များနှင့် k အရောင်များရှိသည်ဟုပေးထားသည်။ ယခုကျွန်ုပ်တို့ပို့စ်များကိုအရောင်တင်ရန်နည်းလမ်းများစွာကိုရှာဖွေရန်လိုအပ်သည်။ တစ်ခုတည်းသောအရောင်နှင့်ကပ်လျက်စာမူ ၂ ခုသာရှိသည်။ နူးညံ့သောချဉ်းကပ်နည်းတစ်ခုမှာကျွန်ုပ်တို့ဖြစ်နိုင်သည် အားလုံးပာ generate ပို့စ်တစ်ခုစီမှရရှိသောအရောင်ကိုဖော်ပြသည်။ သို့သော်ဤချဉ်းကပ်မှုသည်အလွန်ထိရောက်မှုမရှိသောကြောင့်အချိန်ကာလကိုကျော်လွန်သွားနိုင်သည်။

ဒီတော့ဘာပိုကောင်းတဲ့ချဉ်းကပ်မှုဖြစ်နိုင်သလဲ တစ်ခု ချဉ်းကပ်နည်း ကျနော်တို့ပြsmallerနာသေးငယ်သို့ပြိုကွဲလျှင်ဖြစ်နိုင်ပါတယ်။ ပို့စ်အရေအတွက် = n-2 နှင့် n-1 အရေအတွက်သိသည်ကိုစဉ်းစားပါ။ အသီးသီး F (n-2) နှင့် F (n-1) ကို အသုံးပြု၍ ဤတန်ဖိုးများကိုဖော်ပြပါစို့။ ထို့ကြောင့်ကျွန်ုပ်တို့သိရသည်မှာ F (n-1) သည်ကပ်လျက်စာမူ ၂ ခုတည်းသာအရောင်တူညီနိုင်ပြီး F (n-2) နှင့်တူညီသည်။ ယခုကျွန်ုပ်တို့စဉ်းစားသည် (n-2) th နှင့် nth position တွင်တူညီသောအရောင်နှင့်အရောင်တင်လျှင် (n-1) th post တွင် (n-1) nd post ၏အရောင်တူညီမှုမရှိရန်လိုအပ်သည်။ ဤတန်ဖိုးကို F (n-2) ကို အသုံးပြု၍ ဖော်ပြသည်။ ဒါကြောင့်ငါတို့ nth post သည်ပြီးခဲ့သည့် post နှင့်အရောင်တူသောကိစ္စတစ်ခုကိုစဉ်းစားမိသည်။ လက်ရှိစာမူနှင့်နောက်ဆုံးပို့စ်တူအရောင်မတူသင့်သည့်နည်းလမ်းများကိုလည်းစဉ်းစားသင့်သည်။ ဤတန်ဖိုးကို F (n-2) ကို အသုံးပြု၍ ဖော်ပြသည်။ ယခုငါတို့ nth post ကိုအရောင်တင်ရန် (k-1) နည်းလမ်းများရှိသည်။ ထို့ကြောင့်နည်းလမ်းစုစုပေါင်းအရေအတွက် (F (n-1) + F (n-1)) * (--2) နှင့်ညီမျှသည်။

ကုဒ်

Painting Fence Algorithm အတွက် C ++ code

#include <bits/stdc++.h>
using namespace std;

int main(){
  // number of posts
  int n;cin>>n;
  // number of available colors
  int k;cin>>k;
  int mod = 1000000007;
  int ways = 0;
  if(n == 1)cout<<k;
  else if(n == 2)cout<<k*k;
  else {
    int last = k*k; int lastTolast = k;
    for(int i=3;i<=n;i++){
      ways = ((last + lastTolast)*(k-1))%mod;
      lastTolast = last;
      last = ways;
    }
    cout<<ways;
  }
}
4 2
10

Painting Fence Algorithm အတွက် Java code

import java.util.*;
class Main{
    public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
    	// number of posts
    int n = sc.nextInt();
    // number of available colors
    int k = sc.nextInt();
    int mod = 1000000007;
    int ways = 0;
    if(n == 1)System.out.print(k);
    else if(n == 2)System.out.print(k*k);
    else {
      int last = k*k; int lastTolast = k;
      for(int i=3;i<=n;i++){
        ways = ((last + lastTolast)*(k-1))%mod;
        lastTolast = last;
        last = ways;
      }
      System.out.print(ways);
    }
    }
}
4 2
10

ရှုပ်ထွေးဆန်းစစ်ခြင်း

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

အို (N)၊ ကျွန်တော် algorithm ကနေကြည့်ရှုနိုင်သကဲ့သို့။ i သည်ညီမျှသည်အထိလည်ပတ်နေသောတစ်ခုတည်းကွင်းဆက်ကိုအသုံးပြုခဲ့သည်။ ထို့ကြောင့် n အားကြားဖြတ်ခြင်းပြုလုပ်ခြင်းသည်ကျွန်ုပ်တို့သည်အချိန်ရှုပ်ထွေးမှု linear ကိုဆိုလိုသည်။

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

အို (၁)၊  ကျွန်တော်အစားများတဲ့ကိန်းဂဏန်းများကိုသုံးပြီးအစား DP ခင်းကျင်းမှုအဖြစ်အသုံးပြုခဲ့သည်။ ဤချဉ်းကပ်မှုသည် ပို၍ အလားအလာရှိပြီးပြforနာအတွက်ဖြေရှင်းချက်သည်လွန်ခဲ့သောပြsmallerနာနှစ်ခုနှင့်သာသက်ဆိုင်သည်။