အများဆုံးအရှည်မြွေ sequence ကိုရှာပါ  


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် အမေဇုံ CodeNation Expedia Yandex
Dynamic Programming matrix

ပြmaximumနာ“ အများဆုံးအရှည်ရှာတွေ့နိုင်သည့်မြွေအစီအစဉ်ကိုရှာပါ” ကကျွန်ုပ်တို့အားတစ် ဦး ပေးထားကြောင်းဖော်ပြသည် ဇယားကွက် င် ကိန်း။ ၎င်းသည်အမြင့်ဆုံးအရှည်ရှိသောမြွေစဉ်ဆက်မပြတ်ရှာဖွေရန်ဖြစ်သည်။ 1 လုံး ၀ ခြားနားချက်ရှိသောဇယားကွက်ထဲတွင်ကပ်လျက်ရှိသောနံပါတ်များပါရှိသည့် sequence ကို Snake sequence ဟုခေါ်သည်။ နံပါတ်တစ်ခုအတွက်ကပ်လျက်ရှိသောဒြပ်စင်များသည်ဂရစ် (လ်) အတွင်းတွင်တည်ရှိပြီးဖြစ်သောကြောင့်ကျန်ရှိနေသောအိမ်နီးချင်းများနှင့်အထက်နံပါတ်များဖြစ်သည်။ ပုံမှန်အားဖြင့်ပြောရလျှင်သင်သည်ဇယားကွက်ထဲတွင် (i, j) ဆဲလ်တွင်ရပ်နေပါကဆဲလ်များ (i, j-1), (i-1, j) သည်၎င်းနှင့်ကပ်လျက်ရှိပြီး၎င်းတို့သည်ဇယားကွက်အတွင်း၌တည်ရှိသည်။

နမူနာ  

3 3// dimensions of grid
1 2 3
2 4 5
1 2 1
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

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

အများဆုံးအရှည်မြွေ sequence ကိုရှာပါတွယ်အပ်

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

ပြနာကအမြင့်ဆုံးအရှည်ရှိတဲ့မြွေစဉ်ဆက်မပြတ်ဆက်နွယ်မှုကိုရှာရန်ကျွန်ုပ်တို့အားမေးသည်။ နုံသို့မဟုတ် brute force ချဉ်းကပ်မှုတစ်ခုသည် grid ၏ဘယ်ဘက်အပေါ်ထောင့်မှစတင်ရန်နှင့် recursion ကိုအသုံးပြုခြင်းသည်၎င်း၏ညာဖက်နှင့်အောက်ဆုံးအိမ်နီးချင်းကိုဖြတ်သန်းသွားသည်။ အလားတူထိုဆဲလ်များမှသူတို့၏အိမ်နီးချင်းများသို့သွားပါ၊ သို့မှသာသင်ဆဲလ်တစ်ခုမတွေ့ရှိမချင်းဆက်တိုက်ရွေ့လျားမှုသည်ချမှတ်ထားသောအခြေအနေများကြောင့်ရွေးချယ်စရာတစ်ခုမဟုတ်ပါ။ ယေဘုယျအားဖြင့်ကျွန်ုပ်တို့တွင် recursive ဖုန်းခေါ်ဆိုမှုလေးခုရှိသော recursion ကို အသုံးပြု၍ အချိန်ရှုပ်ထွေးမှုသည်ပိုမိုမြင့်မားသောဘက်တွင်ရှိနေသည်။

လည်းကြည့်ရှုပါ
ပေးစာဖြစ်ရပ်မှန် permutation

အထက်ဖော်ပြပါချဉ်းကပ်ပုံအစား၊ Dynamic Programming ဘာဖြစ်လို့လဲဆိုတော့ငါတို့က recursive solution ကိုသုံးပြီးပြproblemနာကိုဖော်ပြတယ်။ ထို့နောက်အဖြေကိုအကောင်းဆုံးဖြစ်စေရန်၎င်းကိုမှတ်သားထားပါ။ အထက်ပါချဉ်းကပ်မှုအတွက်အချိန်ရှုပ်ထွေးခြင်းသည်အဆရှိသော်လည်းအသုံးပြုသည် dynamic programming ကို polynomial ကလျှော့ချနိုင်ပါတယ်။ ဤပြproblemနာအတွက်ကျွန်ုပ်တို့သည်ပြည်နယ်နှစ်ခုကိုပထမ ဦး စွာကြည့်မည်ဆိုလျှင် row index နှင့် column index ဖြစ်သည်။ DP ဇယားရှိဆဲလ်တစ်ခုစီသည်၎င်း၏အထက်နှင့်လက်ဝဲဘက်ဆဲလ်အပေါ်မူတည်လိမ့်မည်။ အဖြေအတွက်ရွေးချယ်ထားသည့်ဆဲလ်များကိုလည်းကျွန်ုပ်တို့လိုအပ်ပါကကျွန်ုပ်တို့သည် DP စားပွဲပေါ်မှလာပြီးဆဲလ်တစ်ခုစီ၏ရလဒ်အနေဖြင့်ဖြတ်သန်းသွားသည်။ မည်သည့်ဆဲလ်ကို လိုက်၍ ဖွဲ့စည်းထားကြောင်းဆုံးဖြတ်သည်။

ကုဒ်  

အများဆုံးအရှည်မြွေအစီအစဉ်ကိုရှာရန် C ++ ကုဒ်

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

int main()
{
    int n=3, m=3;
  int grid[n][m] =
  {
    {1, 2, 3},
    {2, 4, 5},
    {1, 2, 1}
  };

  int dp[n][m];
  int mx = 0, en_i = -1, en_j = -1;
  for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            dp[i][j] = 1;
            if(i>0 && abs(grid[i-1][j]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i-1][j]+1, dp[i][j]);
            if(j>0 && abs(grid[i][j-1]-grid[i][j]) == 1)
                dp[i][j] = max(dp[i][j-1]+1, dp[i][j]);
            if(dp[i][j] > mx){
                mx = dp[i][j];
                en_i = i;
                en_j = j;
            }
        }
  }
  cout<<"Maximum length of the Snake Sequence is: "<<mx<<endl;
  cout<<"The maximum length snake sequence is: ";
  int l_i = -1, l_j = -1;
  while(en_i != l_i || en_j != l_j){
        cout<<grid[en_i][en_j]<<" ";
        l_i = en_i, l_j = en_j;
        if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
            en_i--;
        else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
            en_j--;
  }
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

အများဆုံးအရှည်မြွေကွင်းဆက်ကိုရှာဖွေရန် Java ကုဒ်

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n=3, m=3;
    int grid[][] =
    {
      {1, 2, 3},
      {2, 4, 5},
      {1, 2, 1}
    };

    int dp[][] = new int[n][m];
    int mx = 0, en_i = -1, en_j = -1;
    for(int i=0;i<n;i++){
          for(int j=0;j<m;j++){
              dp[i][j] = 1;
              if(i>0 && Math.abs(grid[i-1][j]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i-1][j]+1, dp[i][j]);
              if(j>0 && Math.abs(grid[i][j-1]-grid[i][j]) == 1)
                  dp[i][j] = Math.max(dp[i][j-1]+1, dp[i][j]);
              if(dp[i][j] > mx){
                  mx = dp[i][j];
                  en_i = i;
                  en_j = j;
              }
          }
    }
    System.out.println("Maximum length of the Snake Sequence is: "+mx);
    System.out.print("The maximum length snake sequence is: ");
    int l_i = -1, l_j = -1;
    while(en_i != l_i || en_j != l_j){
          System.out.print(grid[en_i][en_j]+" ");
          l_i = en_i; l_j = en_j;
          if(en_i > 0 && dp[en_i][en_j] == dp[en_i-1][en_j] + 1)
              en_i--;
          else if(en_j > 0 && dp[en_i][en_j] == dp[en_i][en_j-1] + 1)
              en_j--;
    }
  	}
}
Maximum length of the Snake Sequence is: 5
The maximum length snake sequence is: 1 2 1 2 1

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

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

အို (N * M)၊ ဘယ်မှာ N နှင့် M အသီးသီးအတန်းနှင့်ကော်လံ၏နံပါတ်ဖြစ်ကြသည်။ အချိန်ရှုပ်ထွေးမှုသည်ဇယားကွက်၏အရွယ်အစားပေါ်တွင်မူတည်သည်။ ဘာလို့လဲဆိုတော့ဒါကဇယားကွက်ထဲမှာရှိတဲ့ဆဲလ်အရေအတွက်ကိုတွက်ချက်ရန်လိုအပ်လို့ပဲ။ ထို့ကြောင့်အဆိုးဆုံးမြင်ကွင်းတွင်ကျွန်ုပ်တို့သည်ဇယားကွက်တစ်ခုလုံးကိုသွားရန်လိုအပ်သည်။

လည်းကြည့်ရှုပါ
Newman-Conway အဆက်မပြတ်၏ n ဝေါဟာရများကိုပုံနှိပ်ပါ

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

အို (N * M)၊ ဘာလို့လဲဆိုတော့ကျွန်တော်တို့ဟာ input ဇယားကွက်ရဲ့အရွယ်အစားတူ DP ဇယားကွက်ကိုဖန်တီးသည်။