ផ្លូវផលបូកអប្បបរមានៅក្នុងត្រីកោណ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg
អារេ ការសរសេរកម្មវិធីឌីណាមិក

សេចក្តីថ្លែងការណ៍បញ្ហា។

បញ្ហា“ មាគ៌ាផលបូកអប្បបរមានៅក្នុងត្រីកោណ” ចែងថាអ្នកត្រូវបានគេផ្តល់លំដាប់ជាទម្រង់ត្រីកោណនៃចំនួនគត់។ ឥឡូវចាប់ផ្តើមពីជួរខាងលើតើអ្វីទៅជាផលបូកអប្បបរមាដែលអ្នកអាចទទួលបាននៅពេលអ្នកឈានដល់ជួរខាងក្រោម?

ឧទាហរណ៍

ផ្លូវផលបូកអប្បបរមានៅក្នុងត្រីកោណ

  1
 2 3
5 8 1
5

ការពន្យល់
អ្នកអាចផ្លាស់ទីតាមវិធីដូចខាងក្រោម។ ១-> ៣-> ១. ដូចនេះផលបូកគឺ ៥. ប្រសិនបើយើងបានទៅដោយវិធីលោភលន់។ យើងអាចទៅជាមួយ ២ ជំនួស ៣ ។ ដូចនេះយើងអាចបញ្ចប់ត្រឹមតែ ៨ ឬ ១១ ដែលធំជាង ៥ ។

វិធីសាស្រ្ត

ដូច្នេះតើយើងដោះស្រាយផ្លូវបូកអប្បបរមាក្នុងត្រីកោណយ៉ាងដូចម្តេច? យើងក៏បានដោះស្រាយបញ្ហាស្រដៀងគ្នានេះដែរដែលយើងត្រូវរកវាឃើញ ផ្លូវផលបូកអតិបរមាក្នុងត្រីកោណ។ នៅក្នុងការចុះផ្សាយមុននោះយើងបានពិភាក្សារួចហើយថាវិធីសាស្រ្តនៃកម្លាំងដ៏ម៉ឺងម៉ាត់សម្រាប់បញ្ហាទាំងនេះគឺដើម្បីបង្កើតគ្រប់ផ្លូវ បន្ទាប់ពីជំនាន់នៃផ្លូវទាំងនេះគ្រាន់តែគណនាផលបូកសម្រាប់ផ្លូវនីមួយៗហើយធ្វើបច្ចុប្បន្នភាពផលបូកអប្បបរមា។

ដូច្នេះជំនួសឱ្យការដោះស្រាយបញ្ហានេះដោយប្រើកម្លាំងដុសខាត់យើងដោះស្រាយវាជាមួយ ការសរសេរកម្មវិធីថាមវន្ត។ ដោយសារតែវិធីសាស្រ្តកម្លាំង brute គឺមិនមានប្រសិទ្ធភាពខ្ពស់។

ដំបូងយើងបំពេញចម្លើយសម្រាប់កោសិកានៅជួរចុងក្រោយ។ យើងដឹងថាផលបូកអប្បបរមាដែលអាចទទួលបានគឺប្រសិនបើយើងចាប់ផ្តើមពីកោសិកានៅជួរខាងក្រោមគឺជាលេខខ្លួនឯង។ បន្ទាប់ពីនោះយើងរំកិលទៅជួរខាងលើជួរខាងក្រោម។ សម្រាប់ក្រឡានីមួយៗនៅជួរដេកបច្ចុប្បន្នយើងអាចជ្រើសរើសតម្លៃឌីភីនៃកោសិកាដែលនៅជាប់នឹងវានៅជួរខាងក្រោមក្រោមវា។ ហើយបំពេញតម្លៃអប្បបរមាដែលអាចសម្រេចបាន។ វិធីនេះយើងបន្តទៅមុខទៀត។ នៅពេលយើងឈានដល់ជួរខាងលើយើងត្រូវបានធ្វើរួចជាមួយបញ្ហា។

កូដ C ++ ដើម្បីរកផលបូកផ្លូវអប្បបរមាក្នុងត្រីកោណ

#include<bits/stdc++.h>
using namespace std;
int minimumPathSumInTriangle(vector<vector<int>> &input)
{
    int n = input.size();
    // start from row above bottom row
    // since the bottom row cells are the answers themselves
  for(int i=n-2;i>=0;i--)
  {
      // start from left to right in column
    for(int j=0;j<=i;j++)
    {
      if(input[i+1][j] < input[i+1][j+1])
        input[i][j] += input[i+1][j];
      else
        input[i][j] += input[i+1][j+1];
    }
  }
  return input[0][0];
}
int main()
{
    int n;cin>>n; // number of rows
    vector<vector<int>> input(n, vector<int>(n, 0));
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
    }
    cout<<minimumPathSumInTriangle(input);
}
3
1
2 3
5 8 1
5

កូដចាវ៉ាដើម្បីរកផលបូកផ្លូវអប្បបរមាក្នុងត្រីកោណ

import java.util.*;
class Main{
  static int minimumPathSumInTriangle(int input[][], int n)
  {
      // start from row above bottom row
      // since the bottom row cells are the answers themselves
    for(int i=n-2;i>=0;i--)
    {
        // start from left to right in column
      for(int j=0;j<=i;j++)
      {
        if(input[i+1][j] < input[i+1][j+1])
          input[i][j] += input[i+1][j];
        else
          input[i][j] += input[i+1][j+1];
      }
    }
    return input[0][0];
  }
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt(); // number of rows
      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();
      }
      int answer = minimumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
5

ការវិភាគស្មុគស្មាញ

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

O (N ^ ២)ដូចដែលយើងបានផ្លាស់ប្តូរឆ្លងកាត់ជួរនីមួយៗនិងជួរឈរនីមួយៗ។ នៅក្នុងដំណើរការយើងបានធ្វើដំណើរទៅកាន់កោសិកានីមួយៗ។ ហើយចាប់តាំងពីមានកោសិកា O (N ^ 2) នៅក្នុងត្រីកោណហើយការផ្លាស់ប្តូរសម្រាប់ឌីភីមានតែប្រតិបត្តិការ O (1) ប៉ុណ្ណោះ។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាក៏មានលក្ខណៈពហុធាផងដែរ។

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

O (N ^ ២) ចាប់តាំងពីយើងបានបង្កើតអាដាប់ធ័រឌី។ ឌី។ អេ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហក៏មានពហុធាផងដែរ។