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


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

समस्या वक्तव्य

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

उदाहरणका

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

  1
 2 3
5 8 1
12

स्पष्टीकरण
तपाईं तलको तरिकाले तल पथालिन सक्नुहुन्छ। १-> ->,, यो मार्गले तपाईंलाई अधिकतम योगफल १२ प्राप्त गर्न सक्नेछ।

दृष्टिकोण

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

त्यसोभए यसलाई समाधान गर्न हामीले अर्को दृष्टिकोणको बारेमा सोच्न आवश्यक छ। त्यसो भए गतिशील प्रोग्रामिंग हाम्रो उद्धार गर्न आउँछ। किनभने पथहरू उत्पन्न गर्नुको सट्टा, यदि हामी केहि थाहा पाउन सक्छौं कि अधिकतम के हो जुन सेलबाट प्राप्त गर्न सकिन्छ तल प row्क्तिमा पुग्न। त्यस तरीकाबाट हामी सेलको लागि परिणाम प्राप्त गर्न सक्दछौं जुन त्योसँग नजिक छ तर यसको प the्क्तिमा। त्यसो भए, हामी साना सबप्रोब्लम्सहरू समाधान गर्न DP प्रयोग गर्छौं। त्यसो भए ती सब-समस्याहरूको लागि परिणामहरू मिलाउँदा हामी मूल समस्याको लागि जवाफहरू फेला पार्दछौं।

पहिले, हामी अन्तिम पंक्तिमा कोशिकाको लागि जवाफ भर्दछौं। हामी जान्दछौं कि यदि हामी तल्लो प row्क्तिमा कोशिकाबाट शुरू गर्यौं भने प्राप्त गर्न सकिन्छ अधिकतम योग संख्या हो। त्यस पछि हामी तलको प above्क्ति माथि प to्क्तिमा सर्छौं। हालको प row्क्तिमा प्रत्येक सेलको लागि, हामी सेलहरूको DP मानहरू छनौट गर्न सक्दछौं जुन यो मुनिको पंक्तिमा यसको तल छ। यो बाटो हामी माथिल्लो दिशामा गइरहन्छौं। जब हामी माथिल्लो प row्क्तिमा पुग्दछौं, हामी समस्यासँगै सम्पन्न भयौं

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 ^), हामी प्रत्येक प row्क्ति र प्रत्येक स्तम्भ मा सारिएको रूपमा। प्रक्रियामा, हामी प्रत्येक सेलको लागि यात्रा गर्यौं। र किनकि त्यहाँ त्रिकोणमा O (N ^ 2) सेलहरू थिए र DP का लागि संक्रमणले ओ (१) अपरेसन मात्र लिएको थियो। यसैले, समय जटिलता पनि बहुपद हो।

ठाउँ जटिलता

O (N ^) किनकि हामीले २d DP एर्रे सिर्जना गरेका छौं। यसैले अन्तरिक्ष जटिलता पनि बहुपद हो।