उजव्या संख्येच्या त्रिकोणाच्या पथांची जास्तीत जास्त बेरीज  


अडचण पातळी मध्यम
वारंवार विचारले सिट्रिक्स डीई शॉ डायरेक्टि यामध्ये
डायनॅमिक प्रोग्रामिंग गणित

“राईट नंबर त्रिकोणातील पाथची जास्तीत जास्त बेरीज” ही समस्या आपल्याला सांगते की पूर्णांक उजव्या संख्येच्या त्रिकोणाच्या रूपात. आपण वरुन प्रारंभ केल्यास आणि बेसच्या दिशेने गेल्यास आपण त्याच्या अगदी खाली असलेल्या कक्षात किंवा त्यास उजवीकडे एका जागेवर जाण्यासाठी जास्तीत जास्त बेरीज शोधा.

उदाहरण  

उजव्या संख्येच्या त्रिकोणाच्या पथांची जास्तीत जास्त बेरीज

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

स्पष्टीकरण

शीर्षापासून खालपर्यंत हलवून जास्तीत जास्त बेरीज 15 आहे. हे पुढील चरणांद्वारे मिळवता येते: 1 -> 2 -> १२. वरील प्रतिमेवरून हे अधिक चांगल्या प्रकारे समजू शकते.

दृष्टीकोन  

आमच्याकडे आधीपासूनच या समस्येसारख्या इतर काही समस्या आहेत. आम्ही शोधण्यासाठी समस्या सोडवल्या जास्तीत जास्त, किमान त्रिकोणातील बेरीज पथ. ही समस्या त्या समस्यांमधील थोडा फरक आहे. तर हालचालींवर लागू केलेली अट अशी आहे की आपण चालू सेलच्या अगदी खाली किंवा अगदी उजवीकडे जाऊ शकता. आणि आपण वरच्या शीर्षापासून असलेल्या शीर्षापासून प्रारंभ करा. मग तळ गाठा.

एक मार्ग म्हणजे वापर पुनरावृत्ती. आम्ही एक फंक्शन तयार करू जे इंडेक्सला युक्तिवाद म्हणून घेईल आणि त्या सेलमधून मिळवलेले जास्तीत जास्त शोधू. अशाप्रकारे आम्हाला वारंवार उत्तर सापडते. परंतु यामुळे वेळखाऊ होण्यास त्रास होतो आणि यामुळे वेळेची मर्यादा ओलांडली जाईल. कार्यक्षमतेने समस्या सोडविण्यासाठी. आम्ही या रिकर्सिव कॉलचा परिणाम लक्षात ठेवू शकतो. किंवा वापरा डायनॅमिक प्रोग्रामिंग हे सोडवण्यासाठी. आम्ही तळ-अप पध्दतीवर चर्चा करू जे प्रथम छोट्या उप-समस्यांकरिता निकालाचे गणन करेल आणि नंतर त्या परिणामास एकत्रित केल्यास मूळ समस्येचे उत्तर सापडेल.

हे सुद्धा पहा
अ‍ॅरेमध्ये समीप घटक वेगळे करा

आरंभिक इनपुट अ‍ॅरेच्या सेलने डीपी [0] [0] भरल्यामुळे आम्ही बेस केस परिभाषित करतो. कारण आम्ही या सेलमध्ये इतर कोणत्याही पेशीवर पोहोचू शकत नाही आणि ही एक सुरुवात आहे. यानंतर आपण दुसर्‍या रांगेत जाऊ. येथे आपल्याकडे दोन्ही पेशींसाठी एकच पर्याय आहे. आणि शीर्ष शीर्ष शिरोबिंदू निवडण्याचा पर्याय आहे. त्यानंतर या पंक्तीनंतर, सर्व पेशींसाठी कोणता सेल निवडायचा हे ठरविण्याची आवश्यकता आहे फक्त एक सेल किंवा सध्याच्या सेलच्या डावीकडील सेल. हे सर्व झाल्यानंतर, आम्ही डीपी टेबलच्या शेवटच्या ओळीत जास्तीत जास्त संग्रहित करतो.

कोड  

उजव्या क्रमांकाच्या त्रिकोणामध्ये पाठाची जास्तीत जास्त बेरीज शोधण्यासाठी सी ++ कोड

#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), जेथे एन त्रिकोणातील पंक्तींच्या संख्येचा संदर्भ घेतो. कारण शेवटच्या ओळीत असलेल्या घटकांची संख्या ही आहे.

हे सुद्धा पहा
सर्वात मोठा विभागणीयोग्य जोड्या सबसेट

स्पेस कॉम्प्लेक्सिटी

ओ (1), कारण आम्ही डीपी टेबलसाठी समान इनपुट अ‍ॅरे वापरतो. अशा प्रकारे स्पेस कॉम्प्लेक्सिटी स्थिर असते कारण आम्ही नवीन डीपी अ‍ॅरे तयार करण्यासाठी जागा घेतली नाही.