త్రిభుజంలో కనీస మొత్తం మార్గం


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్
అర్రే డైనమిక్ ప్రోగ్రామింగ్

సమస్యల నివేదిక

“త్రిభుజంలో కనీస మొత్తం మార్గం” అనే సమస్య మీకు పూర్ణాంకాల త్రిభుజం రూపంలో ఒక క్రమాన్ని ఇస్తుందని పేర్కొంది. ఇప్పుడు ఎగువ వరుస నుండి ప్రారంభించి మీరు దిగువ వరుసకు చేరుకున్నప్పుడు మీరు సాధించగల కనీస మొత్తం ఎంత?

ఉదాహరణ

త్రిభుజంలో కనీస మొత్తం మార్గం

  1
 2 3
5 8 1
5

వివరణ
మీరు ఈ క్రింది పద్ధతిలో మార్గం నుండి క్రిందికి వెళ్ళవచ్చు. 1-> 3-> 1. ఈ విధంగా మొత్తం 5. మనం అత్యాశతో వెళ్ళినట్లయితే. మేము 2 కి బదులుగా 3 తో వెళ్ళాము. ఈ విధంగా మనం 8 లేదా అంతకంటే ఎక్కువ 11 లేదా 5 తో మాత్రమే ముగుస్తుంది.

అప్రోచ్

కాబట్టి త్రిభుజంలో కనీస మొత్తం మార్గాన్ని ఎలా పరిష్కరించగలం? మేము కనుగొనవలసిన ఇలాంటి సమస్యను కూడా పరిష్కరించాము త్రిభుజంలో గరిష్ట మొత్తం మార్గం. మునుపటి సమస్యలో, ఈ సమస్యలకు బ్రూట్ ఫోర్స్ విధానం అన్ని మార్గాలను ఉత్పత్తి చేయడమే అని మేము ఇప్పటికే చర్చించాము. ఈ మార్గాల తరం తరువాత, ఈ మార్గాల్లో ప్రతి మొత్తాన్ని లెక్కించండి మరియు కనీస మొత్తాన్ని నవీకరించండి.

కాబట్టి బ్రూట్ ఫోర్స్ ఉపయోగించి ఈ సమస్యను పరిష్కరించడానికి బదులుగా, మేము దీనిని పరిష్కరించాము డైనమిక్ ప్రోగ్రామింగ్. ఎందుకంటే బ్రూట్ ఫోర్స్ విధానం చాలా అసమర్థంగా ఉంటుంది.

మొదట, చివరి వరుసలోని కణాల కోసం మేము సమాధానం నింపుతాము. దిగువ వరుసలోని కణాల నుండి ప్రారంభిస్తే సాధించగల కనీస మొత్తం సంఖ్య అని మాకు తెలుసు. ఆ తరువాత, మేము దిగువ వరుస పైన ఉన్న వరుసకు వెళ్తాము. ప్రస్తుత వరుసలోని ప్రతి సెల్ కోసం, దాని ప్రక్కన ఉన్న కణాల DP విలువలను దాని క్రింద ఉన్న వరుసలో ఎంచుకోవచ్చు. మరియు సాధించగల కనీస విలువను పూరించండి. ఈ విధంగా మనం పైకి వెళ్తూనే ఉంటాము. మేము ఎగువ వరుసకు చేరుకున్నప్పుడు, మేము సమస్యతో పూర్తి చేసాము.

త్రిభుజంలో కనీస మార్గం మొత్తాన్ని కనుగొనడానికి C ++ కోడ్

#include<bits/stdc++.h>
using namespace std;
int minimumPathSumInTriangle(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<<minimumPathSumInTriangle(input);
}
3
1
2 3
5 8 1
5

త్రిభుజంలో కనీస మార్గం మొత్తాన్ని కనుగొనడానికి జావా కోడ్

import java.util.*;
class Main{
  static int minimumPathSumInTriangle(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 = minimumPathSumInTriangle(input, n);
      System.out.print(answer);
  }
}
3
1
2 3
5 8 1
5

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

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

O (N ^ 2), మేము ప్రతి అడ్డు వరుస మరియు ప్రతి కాలమ్‌లోకి వెళ్ళినప్పుడు. ఈ ప్రక్రియలో, మేము ప్రతి సెల్‌కు ప్రయాణించాము. మరియు త్రిభుజంలో O (N ^ 2) కణాలు ఉన్నందున మరియు DP కొరకు పరివర్తన O (1) ఆపరేషన్ మాత్రమే తీసుకుంది. అందువల్ల, సమయ సంక్లిష్టత కూడా బహుపది.

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

O (N ^ 2) మేము 2D DP శ్రేణిని సృష్టించాము కాబట్టి. అందువల్ల స్థల సంక్లిష్టత కూడా బహుపది.