ညာဘက်တြိဂံရှိလမ်းကြောင်း၏အများဆုံးပေါင်းလဒ်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Citrix DE Shaw နေခြည် Expedia
Dynamic Programming သင်္ချာ

“ မှန်ကန်သောနံပါတ်တစ်တြိဂံထဲရှိလမ်းကြောင်း၏အများဆုံးပေါင်းလဒ်” ပြproblemနာကသင့်အားအချို့ပေးသည်ဟုဖော်ပြသည် ကိန်း ညာဘက်နံပါတ်တစ်တြိဂံ၏ပုံစံ၌။ သင်ထိပ်မှ စတင်၍ အခြေခံသို့သွားလျှင်သင်ရရှိနိုင်သောအမြင့်ဆုံးပမာဏကိုရှာဖွေပါ၊ သို့မှသာသင်သည်၎င်းအောက်ရှိဆဲလ်တစ်ခုတည်းသို့သာ၎င်း၏ညာဘက်သို့တစ်နေရာတည်းသို့သာရွေ့လျားနိုင်သည်။

နမူနာ

ညာဘက်တြိဂံရှိလမ်းကြောင်း၏အများဆုံးပေါင်းလဒ်

3 // Number of rows in the right number triangle
1
3 2
4 10 12
15

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

အပေါ်မှအောက်သို့ရွေ့လျားခြင်းဖြင့်ရရှိနိုင်သောအမြင့်ဆုံးပမာဏသည် ၁၅ ဖြစ်သည်။ ၎င်းကိုအောက်ပါအဆင့်များမှရရှိနိုင်သည်။ ၁ -> ၂ -> ၁၂။ အထက်ပါပုံမှ ပို၍ နားလည်နိုင်သည်။

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

ဤပြproblemနာနှင့်ဆင်တူသည့်အခြားပြproblemsနာအချို့ရှိပြီးဖြစ်သည်။ ကျနော်တို့ရှာတွေ့မှပြproblemsနာများကိုဖြေရှင်းခဲ့သည် အများဆုံး, အနည်းဆုံး တြိဂံထဲမှာပေါင်းလဒ်လမ်းကြောင်းကို။ ဤပြproblemနာသည်ထိုပြproblemsနာများ၏အနည်းငယ်ပြောင်းလဲမှုတစ်ခုဖြစ်သည်။ ဒီတော့လှုပ်ရှားမှုအပေါ်ချမှတ်ထားတဲ့အခြေအနေကသင်ဆဲလ်အောက်ဒါမှမဟုတ်ညာဘက်ကိုသွားနိုင်ပါတယ်။ ထိုအခါသင်သည်ထိပ် vertex ကနေထိပ်ကနေစတင်ပါ။ ထိုအခါအောက်ခြေကိုရောက်ရှိ။

နည်းတစ်နည်းမှာအသုံးပြုရန်ဖြစ်သည် ပြန်လည်။ indices များအဖြစ်အငြင်းပွားမှုများအဖြစ်ယူပြီးထိုဆဲလ်မှရရှိနိုင်သောအမြင့်ဆုံးကိုရှာဖွေမည့် function တစ်ခုကိုကျွန်ုပ်တို့ဖန်တီးလိမ့်မည်။ ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်အဖြေကိုပြန်လည်တုံ့ပြန်သည်။ သို့သော်၎င်းသည်ပြtheနာကိုအချိန်ကုန်စေပြီးအချိန်ကာလကိုကျော်လွန်စေနိုင်သည်။ ထို့ကြောင့်ထိရောက်စွာပြtheနာကိုဖြေရှင်းရန်။ ဤပြန်လည်ခေါ်ယူမှုခေါ်ဆိုမှုများ၏ရလဒ်ကိုကျွန်ုပ်တို့အလွတ်ကျက်နိုင်သည်။ ဒါမှမဟုတ်အသုံးပြုပါ Dynamic Programming ဒါကိုဖြေရှင်းဖို့။ အောက်ခြေမှချဉ်းကပ်နည်းကို ဦး စွာဆွေးနွေးပါမည်၊ ၎င်းသည်သေးငယ်သောပြproblemsနာငယ်များအတွက်ရလဒ်ကို ဦး စွာတွက်ချက်ပြီးနောက်ထိုရလဒ်များကိုပေါင်းစပ်။ မူလပြproblemနာအတွက်အဖြေကိုရှာဖွေပါလိမ့်မည်။

အခြေခံအားဖြင့် DP [0] [0] ကို input input array ၏ဆဲလ်ဖြင့်ဖြည့်သည်။ ဘာလို့လဲဆိုတော့ဒီဆဲလ်ကိုအခြားဆဲလ်တစ်ခုမှမရောက်ရှိနိုင်လို့ပါ။ နောက်မှဒုတိယတန်းသို့သွားသည်။ ဒီမှာငါတို့ဆဲလ်နှစ်ခုလုံးအတွက်တစ်ခုတည်း option ရှိသည်။ နှင့် option ကိုထိပ် vertex ဆဲလ်ကိုရွေးချယ်ဖို့ဖြစ်ပါတယ်။ ထိုအခါဤအတန်းပြီးနောက်, ငါတို့ရှိသမျှသည်ဆဲလ်တွေအဘို့, ငါတို့ဆဲလ်ဖို့ပဲဆဲလ်ဖို့ဒါမှမဟုတ်လက်ရှိဆဲလ်၏ဘယ်ဘက်ခြမ်းသောဆဲလ်ကိုရွေးချယ်ဖို့ဘယ်ဆဲလ်ဆုံးဖြတ်ရန်လိုအပ်သည်။ ဤအရာအားလုံးပြီးဆုံးသွားသောအခါ၊ ကျွန်ုပ်တို့သည်နောက်ဆုံး dp စားပွဲ၏နောက်ဆုံးတန်း၌သိုလှောင်ထားသည့်ပမာဏကိုအများဆုံးယူသည်။

ကုဒ်

Right Number Triangle တွင်လမ်းကြောင်းတစ်ခု၏အများဆုံးပေါင်းလဒ်ကိုရှာရန် C ++ ကုဒ်

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

int main(){
    int n;cin>>n;
    int input[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
  if (n > 1)
    input[1][1] = input[1][1] + input[0][0];
    input[1][0] = input[1][0] + input[0][0];
  for(int i = 2; i < n; i++){
        // because the boundary cells have only a single option
    input[i][0] = input[i][0] + input[i-1][0];
    input[i][i] = input[i][i] + input[i-1][i-1];
    for (int j = 1; j < i; j++)
            input[i][j] = input[i][j] + max(input[i-1][j-1], input[i-1][j]);
  }

  int ans = INT_MIN;
  for(int i=0;i<n;i++)
        ans = max(ans, input[n-1][i]);
  cout<<ans;
}
3
1
3 2
4 10 12
15

Right Number Triangle တွင်လမ်းကြောင်း၏အများဆုံးပမာဏကိုရှာရန် Java ကုဒ်ဖြစ်သည်

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int input[][] = new int[n][n];
      for(int i=0;i<n;i++)
          for(int j=0;j<=i;j++)
              input[i][j] = sc.nextInt();;
    if (n > 1)
      input[1][1] = input[1][1] + input[0][0];
      input[1][0] = input[1][0] + input[0][0];
    for(int i = 2; i < n; i++){
          // because the boundary cells have only a single option
      input[i][0] = input[i][0] + input[i-1][0];
      input[i][i] = input[i][i] + input[i-1][i-1];
      for (int j = 1; j < i; j++)
              input[i][j] = input[i][j] + Math.max(input[i-1][j-1], input[i-1][j]);
    }

    int ans = Integer.MIN_VALUE;
    for(int i=0;i<n;i++)
          ans = Math.max(ans, input[n-1][i]);
    System.out.println(ans);
  }
}
3
1
3 2
4 10 12
15

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

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

အို (N ^ 2) N သည်တြိဂံအတွင်းရှိအတန်းအရေအတွက်ကိုရည်ညွှန်းသည်။ ဘာဖြစ်လို့လဲဆိုတော့ဒါကနောက်ဆုံးအတန်းမှာပါတဲ့ element အရေအတွက်ဖြစ်တယ်။

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

အို (၁)၊ ဘာလို့လဲဆိုတော့ကျနော်တို့ DP table အတွက်တူညီတဲ့ input array ကိုသုံးတာပဲ။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် DP ခင်းကျင်းမှုအသစ်တစ်ခုဖန်တီးရန်နေရာမယူသောကြောင့်၊