ထူးခြားသော Paths ကို II


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ VMware က
Dynamic Programming matrix

ပထမဆဲလ်ဒါမှမဟုတ်ဘယ်ဘက်အပေါ်ထောင့်မှာရှိတဲ့လူတစ်ယောက်ဆိုပါစို့ “ a × b” matrix ။ လူတစ်ယောက်သည်တက်သည်ဖြစ်စေအောက်သို့ရွေ့လျားနိုင်သည်။ ထိုလူသည်သူ၏ ဦး တည်ရာကိုရောက်လိုပြီး၎င်းအတွက်ထိုနေရာသည်နောက်ဆုံးဆဲလ်ဖြစ်သည် matrix ဒါမှမဟုတ်ညာဘက်အောက်ခြေ။

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

အတားအဆီးတစ်ခုကို 1 အဖြစ်သတ်မှတ်သည်။ အာကာသကို matrix တွင် 0 အဖြစ်သတ်မှတ်သည်။

နမူနာ

input:

[
[0,0,0]
[0,1,0]
[0,0,0]
]

output:

2

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

ဘာဖြစ်လို့လဲဆိုတော့ matrix တစ်ခုလုံးအလယ်မှာအတားအဆီးတစ်ခုတည်းရှိနေလို့ပဲ။ ဒါကထူးခြားတဲ့လမ်းကြောင်းနှစ်ခုပဲ။

  1. Down → Down →ညာ→ညာ
  2. ညာ→ညာ→အောက်→အောက်သို့

ထူးခြားသော Paths ကို II

အထက်ပါပုံတွင်အပြာရောင်မြှားသည်လမ်းကြောင်း ၁ ကိုပြသည်၊ အနီရောင်မြှားသည်လမ်းကြောင်း ၂ ကိုပြသည်။

algorithm

  1. Array [0] [0] တွင်ပထမဆုံးပါဝင်သောဆဲလ်တွင် 1 ရှိမရှိစစ်ဆေးပြီး၎င်းမှရှေ့သို့မရွှေ့နိုင်သောကြောင့်ထူးခြားသောလမ်းကြောင်းများကို ၀ အဖြစ်သို့ပြန်ပို့ပါ။
  2. Array [0] [0] တွင်တန်ဖိုး ၁ မပါရှိပါက array ၏တန်ဖိုးကိုစပါ။ [1] [0] = 0 ။
  3. ယခုခင်းကျင်းပြသထားသည့်ပထမတန်းတန်းကို ဖြတ်၍ ဤဆဲလ်တွင် ၁ ပါ ၀ င်ပါကလက်ရှိဆဲလ်တွင်အတားအဆီးရှိနေပြီးဆဲလ်တစ်ခု၏တန်ဖိုးကို 1. ဟုသတ်မှတ်သည်။ အခြားဆဲလ်၏တန်ဖိုးကိုယခင်ဆဲလ်များကဲ့သို့သတ်မှတ်ထားသည်။ Array [i] [ည] = ခင်းကျင်း [i] [ည -၁] ဖြစ်သည်။
  4. ယခုခင်းကျင်းခြင်း၏ပထမကော်လံကိုတည့်တည့်ပြောင်းခြင်းနှင့်ဤဆဲလ်တွင် ၁ ပါ ၀ င်ပါကလက်ရှိဆဲလ်တွင်အတားအဆီးရှိနေပြီးဆဲလ်၏တန်ဖိုးကိုသုညအဖြစ်သတ်မှတ်သည်။ အခြားဆဲလ်၏တန်ဖိုးကိုယခင်ဆဲလ်အဖြစ်သတ်မှတ်ထားသည်။ Array [i] [ည] = ခင်းကျင်း [i] [ည -၁] ဖြစ်သည်။
  5. ယခုဆဲလ်ခင်းမှ [1] [1] မှစတင်သည့် matrix တစ်ခုလုံးအပေါ်တွင် ထပ်၍ လုပ်ပါ။
  6. ဆဲလ်တွင်အတားအဆီးမပါရှိမရှိစစ်ဆေးပါ။ ထို့နောက် arrayi၊ j] = array [i-1, j] + array [i, j-1] လုပ်ပါ။
  7. အကယ်၍ ဆဲလ်တစ်ခုတွင်အတားအဆီးတစ်ခုရှိပါက၎င်းသည်အခြားလမ်းကြောင်းတစ်လျှောက်တွင်ထပ်ခါတလဲလဲမရှိစေရန်အတွက်ဆဲလ်၏တန်ဖိုးကို 0 ထားပါ။

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

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

ဒါကြောင့်ငါတို့ပြproblemနာကိုဖြေရှင်းဖို့ကူညီမယ့်လုပ်ဆောင်ချက်အချို့ကိုအကောင်အထည်ဖော်ခဲ့တယ်။ getVal ဆိုတဲ့ function ကိုကြေငြာခဲ့တယ်၊ getVal ကအငြင်းပွားမှုအချို့ကိုအချို့သောလုပ်ဆောင်မှုများကိုလုပ်ဆောင်ပြီးတန်ဖိုးအချို့ကိုပြန်ပေးသည်။ ၎င်းသည်အောက်ပါပြproblemနာကိုဖြေရှင်းရန်ဖြစ်သည်။

  1. အကယ်၍ ပထမတန်းတွင်ဆဲလ်တစ်ခုတွင်အတားအဆီးတစ်ခုပါရှိလျှင်၎င်းသည်၎င်းကိုတန်ဖိုးကို 0 အဖြစ်သတ်မှတ်သည်။ ၎င်းသည်ယခင်ဆဲလ်၏မူလတန်ဖိုးအတိုင်းတန်ဖိုးသတ်မှတ်လိမ့်မည်။ [i] [j] = array [i] [j-1 ] ။
  2. အကယ်၍ ပထမအတန်းတွင်ဆဲလ်တစ်ခုတွင်အတားအဆီးတစ်ခုပါရှိလျှင်၎င်းသည်၎င်းကိုတန်ဖိုးကို 0 အဖြစ်သတ်မှတ်သည်။ ၎င်းသည်ယခင်ဆဲလ်၏မူလတန်ဖိုးအတိုင်းတန်ဖိုးသတ်မှတ်လိမ့်မည်။ [i] [j] = array [i-1] [j ] ။

နမူနာ

ဒီတော့ Array = {{0,0,0}, {0,1,0}, {0,0,0}} ကိုဥပမာတစ်ခုယူကြစို့။

array ကို findUniquePath သို့ကူးပြောင်းလိုက်တယ်

Array = {{0,0,0}, {0,1,0}, {0,0,0}};

ဒါကြောင့်သူ့ရဲ့ပထမဆုံးဆဲလ် (array) [0] [0] သည် 1 နှင့်မတူပါ။

ဒီတော့ set, ခင်းကျင်း [0] [0] = 1;

ကော်လံကျော်ကြားဖြတ်ခြင်း

i = 1

ခင်းကျင်း [1] [0] == 0 နှင့်ခင်းကျင်း [0] [0] = 1 မှန်လျှင်

ဒီတော့ခင်းကျင်း [1] [0] = 1;

i = 2;

ခင်းကျင်း [2] [0] == 0 နှင့်ခင်းကျင်း [1] [0] = 1 မှန်လျှင်

ဒီတော့ခင်းကျင်း [2] [0] = 1;

ယခုအတန်းကျော်ကြားမှာ

i = 1

ခင်းကျင်း [0] [1] == 0 နှင့်ခင်းကျင်း [0] [0] = 1 မှန်လျှင်

ဒီတော့ခင်းကျင်း [0] [1] = 1;

i = 2;

ခင်းကျင်း [0] [2] == 0 နှင့်ခင်းကျင်း [0] [1] = 1 မှန်လျှင်

ဒီတော့ခင်းကျင်း [0] [2] = 1;

ယခုခင်းကျင်းမှုမှစတင် [1] [1]

ဈ = 1, ည = 1

ခင်းကျင်း [1] [1] == 0 င်မှားယွင်းသောလျှင်

ဒါခင်းကျင်း [1] [1] = 0

ဈ = 1, ည = 2

ခင်းကျင်း [1] [2] == 0 င်မှန်လျှင်

array [i] [j] = array [i-1] [j] + array [i] [j-1];

so array[1][2]=array[0][2]+array[0][1];

array[1][2]=1+1=2;

ဈ = 2, ည = 1

ခင်းကျင်း [2] [1] == 0 င်မှန်လျှင်

ဒါခင်းကျင်း [2] [1] = 0

ဈ = 2, ည = 2

ခင်းကျင်း [2] [2] == 0 င်မှန်လျှင်

array [i] [j] = array [i-1] [j] + array [i] [j-1];

so array[2][2]=array[1][2]+array[2][1];

ခင်းကျင်း [2] [2] = 2 + 0;

ခင်းကျင်း [2] [2] = 2

ဆိုလိုသည်မှာကျွန်ုပ်တို့သည်တန်ဖိုးကို array [2] [2] သို့ပြန်သွားပါမည်။ ဆိုလိုသည်မှာ 2 သည်ကျွန်ုပ်တို့၏လိုအပ်သော output ဖြစ်သည်။

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

Unique Paths II အတွက် C ++ အစီအစဉ်

#include<iostream>
using namespace std;
int getVal(int x, int y)
{
    if(x==0 && y==1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int findUniquePath(int arr[3][3])
{
    if (arr[0][0] == 1)
    {
        return 0;
    }
    arr[0][0] = 1;
    for (int i = 1; i < 3; i++)
    {
        arr[i][0] = getVal(arr[i][0],arr[i-1][0]);
    }
    for (int i = 1; i < 3; i++)
    {
        arr[0][i] = getVal(arr[0][i],arr[0][i-1]);
    }
    for (int i = 1; i < 3; i++)
    {
        for (int j = 1; j < 3; j++)
        {
            if (arr[i][j] == 0)
            {
                arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
            }
            else
            {
                arr[i][j] = 0;
            }
        }
    }
    return arr[2][2];
}
int main()
{
    int inputValue[3][3]= {{0,0,0},
                           {0,1,0},
                           {0,0,0}};
                           
    findUniquePath(inputValue);
    cout<<findUniquePath(inputValue);;
    return 0;
}
2

Unique Paths II အတွက် Java အစီအစဉ်

class uniquePath2 {
  public static int getVal(int x, int y) {
    if (x == 0 && y == 1) {
      return 1;
    } else {
      return 0;
    }
  }
  public static int findUniquePath(int array[][]) {
    if (array[0][0] == 1) {
      return 0;
    }
    array[0][0] = 1;
    for (int i = 1; i<array.length; i++) {
      array[i][0] = getVal(array[i][0], array[i - 1][0]);
    }
    for (int i = 1; i<array[0].length; i++) {
      array[0][i] = getVal(array[0][i], array[0][i - 1]);
    }
    for (int i = 1; i<array.length; i++) {
      for (int j = 1; j<array[i].length; j++) {
        if (array[i][j] == 0) {
          array[i][j] = array[i - 1][j] + array[i][j - 1];
        } else {
          array[i][j] = 0;
        }
      }
    }

    int row = array.length;
    int col = array[0].length;
    return array[row - 1][col - 1];
  }
  public static void main(String[] args) {
    int inputValue[][] = {
      {
        0, 0, 0
      }, {
        0, 1, 0
      }, {
        0, 0, 0
      }
    };
    System.out.println(findUniquePath(inputValue));
  }
}
2

ထူးခြားသော Paths II အတွက်ရှုပ်ထွေးမှုအားသုံးသပ်ခြင်း

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

အို (က×ခ) ဘယ်မှာ a နှင့် b သည်ဆဲလ်တစ်ခုချင်းစီကိုသာကျွန်ုပ်တို့အားပေးသည်ဆိုသည့်ကျွန်ုပ်တို့အားပေးသည့် matrix ထဲတွင်အတန်းနှင့်ကော်လံအရေအတွက်ဖြစ်သည်။

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

အို (၁) ငါတို့သုံးနေကတည်းကအပိုအာကာသအသုံးချလျက်ရှိသည်အဖြစ် dynamic programming ကို.

အညွှန်း