एक सही संख्या त्रिकोण में एक पथ का अधिकतम योग


कठिनाई स्तर मध्यम
में अक्सर पूछा Citrix डीई शॉ डायरेक्टी Expedia
गतिशील प्रोग्रामिंग मठ

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

उदाहरण

एक सही संख्या त्रिकोण में एक पथ का अधिकतम योग

3 // Number of rows in the right number triangle
1
3 2
4 10 12
15

व्याख्या

ऊपर से नीचे की ओर बढ़ते हुए अधिकतम योग 15 हो सकता है। यह निम्न चरणों से प्राप्त किया जा सकता है: 1 -> 2 -> 12. यह उपरोक्त छवि से बेहतर समझा जा सकता है।

दृष्टिकोण

हमारे पास पहले से ही कुछ अन्य समस्याएं हैं जो इस समस्या के समान हैं। हमने समस्याओं का हल ढूंढ लिया था अधिकतम, न्यूनतम एक त्रिकोण में योग पथ। यह समस्या उन समस्याओं की थोड़ी भिन्नता है। तो आंदोलन पर जो शर्त लगाई गई है वह यह है कि आप वर्तमान सेल के ठीक नीचे या ठीक नीचे जा सकते हैं। और आप शीर्ष शीर्ष से शुरू करते हैं। फिर नीचे तक पहुंचें।

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

हम आधार मामले को परिभाषित करते हैं, प्रारंभिक इनपुट सरणी के सेल के साथ DP [0] [0] को भरने के रूप में। क्योंकि हम किसी अन्य सेल से इस सेल तक नहीं पहुँच सकते हैं और यह शुरुआत है। इसके बाद, हम दूसरी पंक्ति में जाते हैं। यहां हमारे पास दोनों सेल के लिए एक ही विकल्प है। और विकल्प शीर्ष शीर्ष सेल को चुनना है। फिर इस पंक्ति के बाद, सभी कोशिकाओं के लिए हमें यह तय करने की आवश्यकता है कि कौन सी सेल को चुनना है या तो सिर्फ सेल या सेल जो कि वर्तमान सेल के बाईं ओर है। यह सब हो जाने के बाद, हम डीपी टेबल की अंतिम पंक्ति में अधिकतम संग्रहित करते हैं।

कोड

C ++ कोड एक सही संख्या त्रिकोण में एक पथ का अधिकतम योग खोजने के लिए

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

int main(){
    int n;cin>>n;
    int input[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<=i;j++)
            cin>>input[i][j];
  if (n > 1)
    input[1][1] = input[1][1] + input[0][0];
    input[1][0] = input[1][0] + input[0][0];
  for(int i = 2; i < n; i++){
        // because the boundary cells have only a single option
    input[i][0] = input[i][0] + input[i-1][0];
    input[i][i] = input[i][i] + input[i-1][i-1];
    for (int j = 1; j < i; j++)
            input[i][j] = input[i][j] + max(input[i-1][j-1], input[i-1][j]);
  }

  int ans = INT_MIN;
  for(int i=0;i<n;i++)
        ans = max(ans, input[n-1][i]);
  cout<<ans;
}
3
1
3 2
4 10 12
15

एक सही संख्या त्रिभुज में पथ का अधिकतम योग ज्ञात करने के लिए जावा कोड

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      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();;
    if (n > 1)
      input[1][1] = input[1][1] + input[0][0];
      input[1][0] = input[1][0] + input[0][0];
    for(int i = 2; i < n; i++){
          // because the boundary cells have only a single option
      input[i][0] = input[i][0] + input[i-1][0];
      input[i][i] = input[i][i] + input[i-1][i-1];
      for (int j = 1; j < i; j++)
              input[i][j] = input[i][j] + Math.max(input[i-1][j-1], input[i-1][j]);
    }

    int ans = Integer.MIN_VALUE;
    for(int i=0;i<n;i++)
          ans = Math.max(ans, input[n-1][i]);
    System.out.println(ans);
  }
}
3
1
3 2
4 10 12
15

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

समय जटिलता

ओ (एन ^ 2), जहाँ N त्रिभुज में पंक्तियों की संख्या को संदर्भित करता है। क्योंकि वह तत्वों की संख्या है जो अंतिम पंक्ति में हैं।

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

ओ (1), क्योंकि हम DP तालिका के लिए समान इनपुट सरणी का उपयोग करते हैं। इस प्रकार अंतरिक्ष जटिलता स्थिर है क्योंकि हमने एक नया डीपी सरणी बनाने के लिए स्थान नहीं लिया है।