အဆင့် ၁၊ ၂ သို့မဟုတ် ၃ ကို သုံး၍ nth stair သို့ရောက်ရန်နည်းလမ်းများကိုရေတွက်ပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် အမေဇုံ CodeNation GE Healthcare Microsoft က Moonfrog ဓာတ်ခွဲခန်း PayPal က Uber
ပေါင်းစပ် Dynamic Programming

ပြstepနာက“ အဆင့် ၁၊ ၂၊ ၃ သုံးပြီး nth stair ကိုရောက်ဖို့နည်းလမ်းတွေကိုရေတွက်ပါ။ ယခုသင်လှေကား၏အဆုံးကိုရောက်ဖို့လိုသည်။ ဒါကြောင့်သင်ဟာအဆင့် ၁၊ ၂ ဒါမှမဟုတ် ၃ ဆင့်သာခုန်နိုင်မယ်ဆိုရင်အဆုံးကိုရောက်ဖို့နည်းလမ်းဘယ်လောက်ရှိသလဲ။

နမူနာ

အဆင့် ၁၊ ၂ သို့မဟုတ် ၃ ကို သုံး၍ nth stair သို့ရောက်ရန်နည်းလမ်းများကိုရေတွက်ပါ

2
2

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

နည်းလမ်း ၂ ခုရှိသည်။ အကြောင်းမှာကျွန်ုပ်တို့သည်မြေပြင်မှဒုတိယအလှမ်းသို့တိုက်ရိုက်ရောက်သော်လည်းကောင်း၊ ပထမလှေကားသို့ ဦး တည်။ သော်လည်းကောင်းရှေ့သို့ရွေ့ခြင်းကြောင့်ဖြစ်သည်

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

ပြနာကလှေကားအဆုံးကိုရောက်ဖို့ကျွန်ုပ်တို့မြေပြင်ကနေစတင်ဖို့နည်းလမ်းပေါင်းစုံကိုမေးတယ်။ ဒီတော့လှေကား ၂ ဆင့်ရှိမယ်။ ထို့နောက်ဖြစ်နိုင်ခြေရှိသည့်နည်းလမ်း (၂) ခုကိုသင်ပထမအဆင့်သို့တိုက်ရိုက်ခြေလှမ်းသို့ပထမအဆင့်သို့ပထမအဆင့်သို့အဆင့် ၂ သို့သွားပါ။ အလားတူစွာကျွန်ုပ်တို့သည်အဆင့် (၁)၊ (၂) သို့မဟုတ် (၃) ကို အသုံးပြု၍ nth stair သို့ရောက်ရှိရန်နည်းလမ်းများကိုရေတွက်ရန်လိုအပ်သည်။

နုံစနစ်သည်ဖြစ်နိုင်သမျှနည်းလမ်းအားလုံးကိုထုတ်ပြီး၎င်းတို့ကိုရေတွက်ရန်ဖြစ်သည်။ သို့သော်ဤချဉ်းကပ်မှုသည်အချိန်ကုန်မည်။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုကိုလျှော့ချရန်ကျွန်ုပ်တို့သည်ကွဲပြားခြားနားသောနည်းလမ်းများကိုစဉ်းစားရမည်။ ကျနော်တို့နုံချဉ်းကပ်မှုမှာဆွေးနွေးတဲ့နည်းလမ်းက ကုထုံး သငျသညျ 0th ခြေလှမ်းကနေစတင်နိုင်ပါသည်ဘယ်မှာဖြေရှင်းချက်။ ထို့နောက် recursive ခေါ်ဆိုမှုတစ်ခုစီတွင် i + 1, i + 2 နှင့် i + 3 ကိုသွားပါ။ သငျသညျ nth ခြေလှမ်းရောက်ရှိသည့်အခါကောင်တာတိုး။ ဤနည်းအဆုံး၌ကောင်တာသည် nth step သို့ရောက်ရန်နည်းလမ်းများစွာကိုသိုလှောင်ထားသည်။ သို့သော်ဤအဆင့်သည်တူညီသောပြproblemsနာများကိုထပ်ခါတလဲလဲတွက်ချက်သည်။ ဒါကြောင့်ငါတို့သုံးတဲ့ဒီဖြေရှင်းချက်ကိုပိုကောင်းအောင်လုပ်ဖို့ Dynamic Programming.

Dynamic Programming solution မှာကျွန်တော်တို့ ith step ကိုရောက်နေတယ်လို့စဉ်းစားမိတယ်။ ထိုအခါ i-step သို့ရောက်ရန်နည်းလမ်းများစွာမှာ i-1 အဆင့်၊ i-2 အဆင့်သို့မဟုတ် i-3 အဆင့်မှဖြစ်သည်။ ဒီတော့တရားဝင်ပြောရလျှင်နည်းလမ်းများ [i] = နည်းလမ်းများ [i-1] + နည်းလမ်းများ [i-2] + နည်းလမ်းများ [i-3] ကို အသုံးပြု၍ ဤပြန်လည်ဖော်ထုတ်ရေးဖော်မြူလာကိုအသုံးပြုသည်။ ငါတို့ပြproblemနာကိုဖြေရှင်းမယ်။

ကုဒ်

အဆင့် ၁၊ ၂ သို့မဟုတ် ၃ ကိုအသုံးပြုပြီး nth stair သို့ရောက်ရှိရန်နည်းလမ်းများကို Co ++ to C ++ code

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

int main(){
    int n;cin>>n;
    int dp[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }
    cout<<dp[n];
}
5
13

အဆင့် ၁၊ ၂၊ ၃ ကိုအသုံးပြုပြီး nth stair သို့ရောက်ရှိရန်နည်းလမ်းများအတွက် Count to Java code

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
    int dp[] = new int[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }

    System.out.print(dp[n]);
  }
}
5
13

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

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

အို (N)၊ ဘာလို့လဲဆိုတော့ nth step အထိ loop ကို run ရမယ်။ ဒီတော့ Dynamic Programming ၏စည်းကမ်းချက်များအရကျွန်တော်တို့မှာ ၀ ကနေ 0 အထိရှိတဲ့တစ်ခုတည်းသောပြည်နယ်တစ်ခုရှိခဲ့ပြီးအကူးအပြောင်းကုန်ကျစရိတ်ကအို (၁) ။ ထို့ကြောင့်အချိန်ရှုပ်ထွေးမှုမှာ linear ဖြစ်သည်။

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

အို (N)၊ ကျွန်တော် 1-D ကို DP ခင်းကျင်းဖန်တီးရန်လိုအပ်ပါတယ်ကတည်းက။ ဖြေရှင်းချက်၏အာကာသရှုပ်ထွေး linear ဖြစ်ပါတယ်။