కుడి సంఖ్య త్రిభుజంలో మార్గం యొక్క గరిష్ట మొత్తం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది సిట్రిక్స్ డిఇ షా డైరెక్టి Expedia ద్వారా
డైనమిక్ ప్రోగ్రామింగ్ మఠం

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

ఉదాహరణ

కుడి సంఖ్య త్రిభుజంలో మార్గం యొక్క గరిష్ట మొత్తం

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

వివరణ

పై నుండి క్రిందికి వెళ్లడం ద్వారా సాధించగల గరిష్ట మొత్తం 15. ఈ క్రింది దశల నుండి దీనిని సాధించవచ్చు: 1 -> 2 -> 12. పై చిత్రం నుండి దీన్ని బాగా అర్థం చేసుకోవచ్చు.

అప్రోచ్

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

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

ప్రారంభ ఇన్పుట్ శ్రేణి యొక్క సెల్ తో DP [0] [0] నింపినట్లు మేము బేస్ కేసును నిర్వచించాము. ఎందుకంటే మనం ఈ కణాన్ని మరే ఇతర సెల్ నుండి చేరుకోలేము మరియు ఇది ప్రారంభం. దీని తరువాత, మేము రెండవ వరుసకు వెళ్తాము. ఇక్కడ మనకు రెండు కణాలకు ఒకే ఎంపిక ఉంది. మరియు టాప్ వెర్టెక్స్ సెల్ ను ఎన్నుకోవడం ఎంపిక. ఈ అడ్డు వరుస తరువాత, అన్ని కణాల కోసం మనం ఏ కణాన్ని ఎన్నుకోవాలో నిర్ణయించుకోవాలి, అది కేవలం సెల్ లేదా ప్రస్తుత సెల్ యొక్క ఎడమ వైపున ఉన్న సెల్. ఇవన్నీ పూర్తయిన తర్వాత, మేము dp పట్టిక యొక్క చివరి వరుసలో నిల్వ చేసిన గరిష్టాన్ని తీసుకుంటాము.

కోడ్

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

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

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

O (N ^ 2), ఇక్కడ N త్రిభుజంలోని వరుసల సంఖ్యను సూచిస్తుంది. ఎందుకంటే అది చివరి వరుసలో ఉన్న మూలకాల సంఖ్య.

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

ఓ (1), ఎందుకంటే మేము DP పట్టిక కోసం ఒకే ఇన్పుట్ శ్రేణిని ఉపయోగిస్తాము. అందువల్ల క్రొత్త DP శ్రేణిని సృష్టించడానికి మేము స్థలాన్ని తీసుకోనందున స్థల సంక్లిష్టత స్థిరంగా ఉంటుంది.