ත්රිකෝණයක අවම එකතුව


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග්
අරා ගතික වැඩසටහන්කරණය

ගැටළු ප්රකාශය

“ත්‍රිකෝණයක අවම එකතුව” යන ගැටලුවේ සඳහන් වන්නේ ඔබට පූර්ණ සංඛ්‍යා ත්‍රිකෝණයක ස්වරූපයෙන් අනුක්‍රමයක් ලබා දෙන බවයි. දැන් ඉහළ පේළියේ සිට ආරම්භ කර පහළ පේළියට ළඟා වූ විට ඔබට ළඟා කර ගත හැකි අවම මුදල කුමක්ද?

උදාහරණයක්

ත්රිකෝණයක අවම එකතුව

  1
 2 3
5 8 1
5

පැහැදිලි කිරීම
ඔබට සරලවම පහත දැක්වෙන ආකාරයට ගමන් කළ හැකිය. 1-> 3-> 1. මේ අනුව එකතුව 5. අප කෑදර ප්‍රවේශයකින් යන්නට තිබුණි නම්. අපි 2 වෙනුවට 3 ක් සමඟ යන්නට ඇත. මේ අනුව අපට අවසන් විය හැක්කේ 8 ට වඩා වැඩි 11 හෝ 5 ක් පමණි.

ප්රවේශය

ඉතින් අපි ත්‍රිකෝණයක අවම එකතුව මාර්ගය විසඳන්නේ කෙසේද? ඒ හා සමාන ගැටලුවක් ද අප විසින් සොයාගෙන ඇත ත්රිකෝණයක උපරිම එකතුව මාර්ගය. මෙම ගැටළු සඳහා තිරිසන් බලවේගය සියලු මාර්ග ජනනය කිරීම බව අපි කලින් ලිපියේ සාකච්ඡා කර ඇත්තෙමු. මෙම මාර්ග උත්පාදනය කිරීමෙන් පසුව, මෙම එක් එක් මාර්ග සඳහා එකතුව ගණනය කර අවම මුදල යාවත්කාලීන කරන්න.

එබැවින් තිරිසන් බලය භාවිතා කරමින් මෙම ගැටළුව විසඳනවා වෙනුවට අපි මෙය විසඳා ගනිමු ගතික වැඩසටහන්කරණය. තිරිසන් බලවේගය ඉතා අකාර්යක්ෂම නිසා.

පළමුව, අපි අවසාන පේළියේ සෛල සඳහා පිළිතුර පුරවන්නෙමු. පහළ පේළියේ ඇති සෛල වලින් අප ආරම්භ කළහොත් ලබා ගත හැකි අවම මුදල සංඛ්‍යාව බව අපි දනිමු. ඊට පසු, අපි පහළ පේළියට ඉහළින් ඇති පේළියට ගමන් කරමු. වත්මන් පේළියේ සෑම සෛලයක් සඳහාම, ඊට පහළින් ඇති පේළියේ එයට යාබදව ඇති සෛලවල ඩීපී අගයන් තෝරා ගත හැකිය. ළඟා කර ගත හැකි අවම අගය පුරවන්න. මේ ආකාරයෙන් අපි දිගටම ඉහළට යනවා. අපි ඉහළ පේළියට ළඟා වන විට, අප ගැටලුව සමඟ කටයුතු කරයි.

ත්රිකෝණයක අවම මාර්ග එකතුව සොයා ගැනීමට 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් ^ 2), අපි එක් එක් පේළිය සහ එක් එක් තීරුව හරහා ගමන් කරන විට. මෙම ක්‍රියාවලියේදී අපි සෑම සෛලයකටම ගමන් කළෙමු. ත්රිකෝණයේ O (N ^ 2) සෛල ඇති බැවින් සහ DP සඳහා සංක්රමණය සිදු වූයේ O (1) ක්රියාකාරිත්වය පමණි. මේ අනුව, කාල සංකීර්ණතාව ද බහුපද වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එන් ^ 2) අපි 2D DP අරාවක් නිර්මාණය කළ නිසා. මේ අනුව අවකාශයේ සංකීර්ණතාව ද බහුපද වේ.