ផ្លូវតែមួយគត់


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon VMware
ការសរសេរកម្មវិធីឌីណាមិក ម៉ាទ្រីស

ឧបមាថាបុរសម្នាក់ឈរនៅបន្ទប់ទីមួយឬជ្រុងខាងឆ្វេងខាងលើ “ a-b” ម៉ាទ្រីស។ បុរសម្នាក់អាចផ្លាស់ទីបានទាំងឡើងឬចុះក្រោម។ មនុស្សនោះចង់ទៅដល់គោលដៅរបស់គាត់ហើយគោលដៅនោះសម្រាប់គាត់គឺជាកោសិកាចុងក្រោយនៃព្រះគម្ពីរមរមន ម៉ាទ្រីស ឬជ្រុងខាងស្តាំផ្នែកខាងក្រោម។

ហើយប្រសិនបើមានឧបសគ្គខ្លះនៅក្នុងវាតើមានផ្លូវប្លែកប៉ុន្មានដែលអាចត្រូវបានកំណត់ដោយបុគ្គលនោះ។ ជួយគាត់ឱ្យទៅដល់គោលដៅដោយស្គាល់ No of Unique Paths ។

ឧបសគ្គត្រូវបានគេចាត់ទុកថាជាលេខ 1 ហើយចន្លោះត្រូវបានសម្គាល់ជា 0 នៅក្នុងម៉ាទ្រីស។

ឧទាហរណ៍

បញ្ចូល:

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

លទ្ធផល:

2

ការពន្យល់:

ពីព្រោះមានតែឧបសគ្គមួយប៉ុណ្ណោះដែលមាននៅពាក់កណ្តាលម៉ាទ្រីសទាំងមូលដែលអនុញ្ញាតឱ្យមានផ្លូវតែមួយគត់ពីរ៖ -

  1. ចុះក្រោម→ចុះក្រោម→ស្ដាំ→ស្តាំ
  2. ស្តាំ→ស្តាំ→ចុះ→ចុះក្រោម

ផ្លូវតែមួយគត់

ក្នុងរូបភាពខាងលើព្រួញពណ៌ខៀវបង្ហាញផ្លូវ ១ និងព្រួញពណ៌ក្រហមបង្ហាញផ្លូវ ២ ។

ក្បួនដោះស្រាយ

  1. ពិនិត្យមើលថាតើកោសិកាទីមួយដែលមានជួរ [0] [0] មាន 1 បន្ទាប់មកត្រឡប់ផ្លូវដែលមានតែមួយដូចជា 0 ព្រោះវាមិនអាចទៅមុខបានជាងនេះ។
  2. ប្រសិនបើអារេ [0] [0] មិនមានតំលៃ 1 បន្ទាប់មកចាប់ផ្តើមតម្លៃនៃអារេ [0] [0] = 1 ។
  3. ឥឡូវវាស្ថិតនៅជួរជួរដេកដំបូងនៃអារេហើយប្រសិនបើក្រឡានេះមាន ១ នេះមានន័យថាកោសិកាបច្ចុប្បន្នមានឧបសគ្គនៅក្នុងវាហើយកំណត់តម្លៃនៃក្រឡាទៅ ០ ។ ផ្សេងទៀតកំណត់តម្លៃនៃក្រឡានេះដូចនឹងក្រឡាមុនដែល គឺអារេ [ខ្ញុំ] [ច] = អារេ [ខ្ញុំ] [ចា - ១] ។
  4. ឥលូវនេះវានៅលើជួរឈរទី ១ នៃអារេហើយប្រសិនបើក្រឡានេះមានលេខ ១ មានន័យថាកោសិកាបច្ចុប្បន្នមានឧបសគ្គនៅក្នុងវាហើយកំណត់តំលៃនៃកោសិកាទៅ ០ ។ ផ្សេងទៀតកំណត់តំលៃនៃកោសិកានេះដូចនឹងកោសិកាមុនដែល គឺអារេ [ខ្ញុំ] [ច] = អារេ [ខ្ញុំ] [ចា - ១] ។
  5. ឥលូវនេះវាមានលក្ខណៈដូចម៉ាទ្រីសទាំងមូលដែលចាប់ផ្តើមពីអារេកោសិកា [1] [1] ។
  6. ពិនិត្យមើលថាតើកោសិកាមិនមានឧបសគ្គអ្វីទេបន្ទាប់មកធ្វើអារេ, ចា] = អារេ [i-1, ចា] + អារេ [i, ជ - ១] ។
  7. ប្រសិនបើក្រឡាមានឧបសគ្គបន្ទាប់មកកំណត់តម្លៃនៃក្រឡាទៅ ០ ដើម្បីធ្វើឱ្យប្រាកដថាវាមិនកើតឡើងម្តងទៀតទេ។

ការពន្យល់

ដូច្នេះគំនិតចម្បងរបស់យើងសម្រាប់ការដោះស្រាយសំណួរនេះគឺប្រសិនបើក្រឡាមួយមិនមានតំលៃ ០ នៅក្នុងនោះវាមានន័យថាយើងមានចំនួនវិធីដើម្បីទៅដល់កោសិកាគោលដៅរបស់យើងគឺជាផលបូកនៃចំនួនវិធីដើម្បីឈានដល់កោសិកាខាងលើ cell និងផលបូកនៃចំនួនវិធីនៃការឈានដល់ cell ដែលនៅសល់នៃ cell នោះ។

ដូច្នេះយើងអនុវត្តមុខងារមួយចំនួនដែលនឹងជួយយើងក្នុងការដោះស្រាយបញ្ហារបស់យើង។ យើងបានប្រកាសមុខងារ getVal, getVal ទទួលបានអាគុយម៉ង់មួយចំនួនអនុវត្តប្រតិបត្ដិការខ្លះហើយត្រឡប់តម្លៃខ្លះដែលនឹងដោះស្រាយបញ្ហាដូចខាងក្រោម៖

  1. ប្រសិនបើនៅជួរទីមួយក្រឡាមានឧបសគ្គវាកំណត់តម្លៃ 0 ផ្សេងទៀតវានឹងកំណត់តម្លៃនៃក្រឡានោះដូចនឹងក្រឡាមុនដែលជាអារេ [i] [ច] = អារេ [i] [ជ 1 ] ។
  2. ប្រសិនបើនៅជួរទីមួយក្រឡាមានឧបសគ្គវាកំណត់តម្លៃ 0 ផ្សេងទៀតវានឹងកំណត់តម្លៃនៃក្រឡានោះដូចនឹងក្រឡាមុនដែលជាអារេ [i] [ច] = អារេ [i-1] [ច។ ] ។

ឧទាហរណ៍

ដូច្នេះសូមយើងពិចារណាឧទាហរណ៍ដូចជាអារេ = {{០,០,០}, {០,១,០}, {០,០,០}};

អារេមួយត្រូវបានបញ្ជូនទៅក្នុង FindUniquePath

អារេ = {{០,០,០}, {០,១,០}, {០,០,០}};

ដូច្នេះកោសិកាដំបូងរបស់វាដែលជាអារេ [០] [០] មិនស្មើនឹង ១ ទេ។

ដូច្នេះកំណត់អារេ [0] [0] = 1;

បំលែងលើជួរឈរ,

i = ៤

បើអារេ [១] [០] == ០ និងអារេ [០] [០] = ១ គឺពិត

ដូច្នេះអារេ [១] [០] = ១;

i = 2;

បើអារេ [១] [០] == ០ និងអារេ [០] [០] = ១ គឺពិត

ដូច្នេះអារេ [១] [០] = ១;

ឥឡូវវាហួសជួរហើយ

i = ៤

បើអារេ [១] [០] == ០ និងអារេ [០] [០] = ១ គឺពិត

ដូច្នេះអារេ [១] [០] = ១;

i = 2;

បើអារេ [១] [០] == ០ និងអារេ [០] [០] = ១ គឺពិត

ដូច្នេះអារេ [១] [០] = ១;

ឥឡូវចាប់ផ្តើមពីអារេ [១] [១]

i = 1, ច = 1

បើអារេ [១] [១] == ០ គឺមិនពិត

ដូច្នេះអារេ [១] [១] = ០

i = 1, ច = 2

បើអារេ [១] [២] == ០ គឺពិត

អារេ [ខ្ញុំ] [ច] = អារេ [អាយ - ១] [ច] + អារេ [ខ្ញុំ] [ច - ​​១];

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

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

i = 2, ច = 1

បើអារេ [១] [២] == ០ គឺពិត

ដូច្នេះអារេ [១] [១] = ០

i = 2, ច = 2

បើអារេ [១] [២] == ០ គឺពិត

អារេ [ខ្ញុំ] [ច] = អារេ [អាយ - ១] [ច] + អារេ [ខ្ញុំ] [ច - ​​១];

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

អារេ [២] [២] = ២ + ០;

អារេ [២] [២] = ២

នោះគឺយើងនឹងត្រឡប់ជួរតម្លៃ [2] [2] ដែលមានន័យថា 2 គឺជាទិន្នផលដែលត្រូវការរបស់យើង។

ការអនុវត្តន៍

កម្មវិធី 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

កម្មវិធីចាវ៉ាសម្រាប់ផ្លូវមានតែមួយ

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

ការវិភាគស្មុគស្មាញសម្រាប់ផ្លូវតែមួយគត់

ស្មុគស្មាញពេលវេលា

O (a × b) ដែល a និង b ជាចំនួនជួរដេកនិងជួរឈរនៅក្នុងម៉ាទ្រីសដែលបានផ្តល់ដល់យើងនៅពេលដែលកោសិកានីមួយៗត្រូវបានដំណើរការតែមួយដង។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ដោយសារគ្មានកន្លែងទំនេរត្រូវបានប្រើប្រាស់ចាប់តាំងពីយើងកំពុងប្រើប្រាស់ ការសរសេរកម្មវិធីថាមវន្ត.

ឯកសារយោង