ත්රිකෝණයක උපරිම මාර්ග එකතුව


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ආකේසියම් කෝඩ්නේෂන් GE සෞඛ්යාරක්ෂණය PayU Uber Zoho
ගතික වැඩසටහන්කරණය

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

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

උදාහරණයක්

ත්රිකෝණයක උපරිම මාර්ග එකතුව

  1
 2 3
5 8 1
12

පැහැදිලි කිරීම
ඔබට සරලවම පහත දැක්වෙන ආකාරයට ගමන් කළ හැකිය. 1-> 3-> 8, මෙම මාර්ගය මඟින් ඔබට උපරිම එකතුව 12 ක් වනු ඇත.

ප්රවේශය

ඉතින් අපි ත්‍රිකෝණයක උපරිම මාර්ග එකතුව විසඳන්නේ කෙසේද? මේ වන තෙක්, අපි මේ ආකාරයේ ගැටළු වලට හුරු පුරුදුය. අපට මේ ආකාරයේ ගැටළු ලබා දෙන සෑම අවස්ථාවකම. තිරිසන් බලවේගය සැමවිටම ඔබේ ගමනාන්තයට ළඟා විය හැකි සියලු මාර්ග ජනනය කිරීමයි. ඉන්පසු එක් එක් මාර්ගය සඳහා එකතුව ගණනය කිරීමෙන් ප්‍රශස්ත ප්‍රති result ල සඳහා පිළිතුර යාවත්කාලීන කරන්න. නමුත් මෙම ප්‍රවේශය අපට මාර්ග උත්පාදනය කිරීමට අවශ්‍ය බැවින් මෙම ප්‍රවේශය බෙහෙවින් අකාර්යක්ෂම වේ. මාර්ග උත්පාදනය යනු on ාතීය කාල සංකීර්ණත්වයක් ඇති කාර්යයක් නොවන බව අපි දනිමු.

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

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

ත්රිකෝණයක උපරිම මාර්ග එකතුව සොයා ගැනීමට C ++ කේතය

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

int maximumPathSumInTriangle(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<<maximumPathSumInTriangle(input);
}

}
3
1
2 3
5 8 1
12

ත්රිකෝණයක උපරිම මාර්ග එකතුව සොයා ගැනීමට ජාවා කේතය

import java.util.*;

class Main{
  static int maximumPathSumInTriangle(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 = maximumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
12

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

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

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

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

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