एक त्रिकोण में अधिकतम पथ योग


कठिनाई स्तर मध्यम
में अक्सर पूछा आर्सेनियम कोडेशन जीई हेल्थकेयर PayU Uber Zoho
गतिशील प्रोग्रामिंग

समस्या का विवरण

समस्या "एक त्रिकोण में अधिकतम पथ राशि" बताती है कि आपको कुछ पूर्णांक दिए गए हैं। ये पूर्णांक एक त्रिकोण के रूप में व्यवस्थित होते हैं। आप त्रिकोण के शीर्ष से शुरू कर रहे हैं और नीचे की पंक्ति तक पहुंचने की आवश्यकता है। ऐसा करने के लिए, आप अगली पंक्ति में आसन्न कोशिकाओं में चले जाते हैं। इसलिए जब आप परिभाषित तरीके से त्रिभुज को नीचे ला रहे हैं, तो आपको प्राप्त होने वाली अधिकतम राशि क्या है?

उदाहरण

एक त्रिकोण में अधिकतम पथ योग

  1
 2 3
5 8 1
12

व्याख्या
आप बस निम्नलिखित तरीके से पथ को नीचे ले जा सकते हैं। 1-> 3-> 8, इस पथ से आपको अधिकतम योग प्राप्त होगा जो कि 12 है।

दृष्टिकोण

तो हम एक त्रिकोण में अधिकतम पथ योग कैसे हल करते हैं? अब तक, हम इस प्रकार की समस्याओं से बहुत परिचित हैं। जब भी हमें इस प्रकार की समस्याएं प्रदान की जाती हैं। जानवर बल दृष्टिकोण हमेशा अपने गंतव्य तक पहुंचने के लिए सभी संभव तरीकों को उत्पन्न करना है। और फिर प्रत्येक पथ के लिए योग की गणना करके, इष्टतम परिणाम के लिए उत्तर को अपडेट करते रहें। लेकिन यह दृष्टिकोण अत्यधिक अक्षम है क्योंकि इस दृष्टिकोण से हमें पथ उत्पन्न करने की आवश्यकता होती है। और हम जानते हैं कि पथ निर्माण एक ऐसा कार्य है जिसमें घातीय समय जटिलता है जो अच्छी नहीं है।

इसलिए, इसे हल करने के लिए हमें एक और दृष्टिकोण के बारे में सोचना होगा। फिर गतिशील प्रोग्रामिंग हमारे बचाव में आता है। क्योंकि रास्ते बनाने के बजाय, अगर हम किसी तरह जान सकते हैं कि अधिकतम क्या है जो एक सेल से नीचे पंक्ति तक पहुंचने के लिए प्राप्त किया जा सकता है। इस तरह से हम उस सेल के लिए परिणाम प्राप्त कर सकते हैं जो इसके निकट है लेकिन इसके ऊपर की पंक्ति में है। तो, हम छोटे उपप्रकारों को हल करने के लिए डीपी का उपयोग करते हैं। फिर उन उपप्रकारों के लिए परिणामों के संयोजन से हमें मूल समस्या के उत्तर मिलते हैं।

सबसे पहले, हम अंतिम पंक्ति में कोशिकाओं के लिए उत्तर भरते हैं। हम जानते हैं कि अगर हम नीचे की पंक्ति में कोशिकाओं से शुरू करते हैं तो अधिकतम राशि प्राप्त की जा सकती है। उसके बाद, हम नीचे की पंक्ति के ऊपर की पंक्ति में जाते हैं। वर्तमान पंक्ति में प्रत्येक सेल के लिए, हम उन कोशिकाओं के 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

जटिलता विश्लेषण

समय जटिलता

ओ (एन ^ 2), जैसा कि हम प्रत्येक पंक्ति और प्रत्येक स्तंभ के पार चले गए। इस प्रक्रिया में, हमने प्रत्येक सेल की यात्रा की। और चूंकि त्रिकोण में ओ (एन ^ 2) कोशिकाएं थीं और डीपी के लिए संक्रमण ने केवल ओ (1) ऑपरेशन किया। इस प्रकार, समय जटिलता भी बहुपद है।

अंतरिक्ष जटिलता

ओ (एन ^ 2) चूँकि हमने एक 2D DP सरणी बनाई है। इस प्रकार अंतरिक्ष की जटिलता भी बहुपद है।