త్రిభుజంలో గరిష్ట మార్గం మొత్తం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది ఆర్సెసియం కోడ్‌నేషన్ GE హెల్త్ PayU ఉబెర్ జోహో
డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

“త్రిభుజంలో గరిష్ట మార్గం మొత్తం” సమస్య మీకు కొన్ని పూర్ణాంకాలు ఇవ్వబడిందని పేర్కొంది. ఈ పూర్ణాంకాలు త్రిభుజం రూపంలో అమర్చబడి ఉంటాయి. మీరు త్రిభుజం ఎగువ నుండి ప్రారంభిస్తున్నారు మరియు దిగువ వరుసకు చేరుకోవాలి. ఇలా చేయడం కోసం, మీరు తదుపరి వరుసలోని ప్రక్కన ఉన్న కణాలకు వెళతారు. కాబట్టి మీరు నిర్వచించిన పద్ధతిలో త్రిభుజానికి క్రిందికి కదులుతున్నప్పుడు, మీరు సాధించగల గరిష్ట మొత్తం ఎంత?

ఉదాహరణ

త్రిభుజంలో గరిష్ట మార్గం మొత్తం

  1
 2 3
5 8 1
12

వివరణ
మీరు ఈ క్రింది పద్ధతిలో మార్గం నుండి క్రిందికి వెళ్ళవచ్చు. 1-> 3-> 8, ఈ మార్గం మీకు గరిష్ట మొత్తాన్ని 12 గా చేస్తుంది.

అప్రోచ్

కాబట్టి త్రిభుజంలో గరిష్ట మార్గం మొత్తాన్ని ఎలా పరిష్కరించగలం? ఇప్పటి వరకు, ఈ రకమైన సమస్యలతో మనకు బాగా తెలుసు. మనకు ఈ రకమైన సమస్యలను అందించినప్పుడల్లా. బ్రూట్ ఫోర్స్ విధానం ఎల్లప్పుడూ మీ గమ్యాన్ని చేరుకోవడానికి సాధ్యమయ్యే అన్ని మార్గాలను రూపొందించడం. ఆపై ప్రతి మార్గం కోసం మొత్తాన్ని లెక్కించడం ద్వారా సరైన ఫలితం కోసం సమాధానాన్ని నవీకరించడం కొనసాగించండి. కానీ ఈ విధానం చాలా అసమర్థంగా ఉంటుంది, ఎందుకంటే ఈ విధానం మనకు మార్గాలను రూపొందించాల్సిన అవసరం ఉంది. పాత్ జనరేషన్ అనేది ఘాతాంక సమయ సంక్లిష్టతను కలిగి ఉన్న పని అని మనకు తెలుసు.

కాబట్టి, దీనిని పరిష్కరించడానికి మనం మరొక విధానం గురించి ఆలోచించాలి. అప్పుడు డైనమిక్ ప్రోగ్రామింగ్ మా రక్షణకు వస్తుంది. ఎందుకంటే మార్గాలను ఉత్పత్తి చేయడానికి బదులుగా, కణం నుండి దిగువ వరుసకు చేరుకోవడానికి గరిష్టంగా ఏది అని మనకు తెలుసు. ఆ విధంగా మనం దాని ప్రక్కనే ఉన్న సెల్ కోసం ఫలితాన్ని పొందవచ్చు కాని దాని పైన ఉన్న వరుసలో. కాబట్టి, చిన్న ఉప సమస్యలను పరిష్కరించడానికి మేము DP ని ఉపయోగిస్తాము. ఆ ఉప సమస్యల కోసం ఫలితాలను కలపడం ద్వారా అసలు సమస్యకు సమాధానాలు దొరుకుతాయి.

మొదట, చివరి వరుసలోని కణాల కోసం మేము సమాధానం నింపుతాము. దిగువ వరుసలోని కణాల నుండి ప్రారంభిస్తే సాధించగల గరిష్ట మొత్తం సంఖ్య అని మాకు తెలుసు. ఆ తరువాత, మేము దిగువ వరుస పైన ఉన్న వరుసకు వెళ్తాము. ప్రస్తుత వరుసలోని ప్రతి సెల్ కోసం, దాని ప్రక్కన ఉన్న కణాల DP విలువలను దాని క్రింద ఉన్న వరుసలో ఎంచుకోవచ్చు. ఈ విధంగా మనం పైకి వెళ్తూనే ఉంటాము. మేము ఎగువ వరుసకు చేరుకున్నప్పుడు, మేము సమస్యతో పూర్తి చేసాము.

త్రిభుజంలో గరిష్ట మార్గం మొత్తాన్ని కనుగొనడానికి 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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N ^ 2), మేము ప్రతి అడ్డు వరుస మరియు ప్రతి కాలమ్‌లోకి వెళ్ళినప్పుడు. ఈ ప్రక్రియలో, మేము ప్రతి సెల్‌కు ప్రయాణించాము. మరియు త్రిభుజంలో O (N ^ 2) కణాలు ఉన్నందున మరియు DP కొరకు పరివర్తన O (1) ఆపరేషన్ మాత్రమే తీసుకుంది. అందువల్ల, సమయ సంక్లిష్టత కూడా బహుపది.

అంతరిక్ష సంక్లిష్టత

O (N ^ 2) మేము 2D DP శ్రేణిని సృష్టించాము కాబట్టి. అందువల్ల స్థల సంక్లిష్టత కూడా బహుపది.