ஒரு முக்கோணத்தில் அதிகபட்ச பாதை தொகை


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது ஆர்சீசியம் கோட்நேஷன் GE ஹெல்த்கேர் PayU கிழித்து ஸோகோ
டைனமிக் புரோகிராமிங்

சிக்கல் அறிக்கை

“ஒரு முக்கோணத்தில் அதிகபட்ச பாதை தொகை” என்ற சிக்கல் உங்களுக்கு சில முழு எண்களை வழங்கியுள்ளது என்று கூறுகிறது. இந்த முழு எண்கள் ஒரு முக்கோண வடிவில் அமைக்கப்பட்டிருக்கும். நீங்கள் முக்கோணத்தின் மேலிருந்து தொடங்குகிறீர்கள், மேலும் கீழ் வரிசையை அடைய வேண்டும். இதைச் செய்ய, அடுத்த வரிசையில் உள்ள அருகிலுள்ள கலங்களுக்குச் செல்கிறீர்கள். எனவே நீங்கள் முக்கோணத்தை வரையறுக்கப்பட்ட முறையில் நகர்த்தும்போது, ​​நீங்கள் அடையக்கூடிய அதிகபட்ச தொகை என்ன?

உதாரணமாக

ஒரு முக்கோணத்தில் அதிகபட்ச பாதை தொகை

  1
 2 3
5 8 1
12

விளக்கம்
நீங்கள் பின்வரும் வழியில் பாதையில் செல்லலாம். 1-> 3-> 8, இந்த பாதை உங்களை அதிகபட்சமாக 12 ஆக அடையச் செய்யும்.

அணுகுமுறை

எனவே ஒரு முக்கோணத்தில் அதிகபட்ச பாதை தொகையை எவ்வாறு தீர்ப்பது? இப்போது வரை, இந்த வகையான சிக்கல்களை நாங்கள் நன்கு அறிந்திருக்கிறோம். எப்போது இந்த வகையான பிரச்சினைகள் நமக்கு வழங்கப்படுகின்றன. உங்கள் இலக்கை அடைய சாத்தியமான அனைத்து வழிகளையும் முதலில் உருவாக்குவதே முரட்டுத்தனமான அணுகுமுறை. ஒவ்வொரு பாதைக்குமான தொகையை கணக்கிடுவதன் மூலம், உகந்த முடிவுக்கான பதிலைப் புதுப்பித்துக்கொண்டே இருங்கள். ஆனால் இந்த அணுகுமுறை மிகவும் திறமையற்றது, ஏனெனில் இந்த அணுகுமுறை எங்களுக்கு பாதைகளை உருவாக்க வேண்டும். பாதை உருவாக்கம் என்பது அதிவேக நேர சிக்கலைக் கொண்ட ஒரு பணி என்பதை நாங்கள் அறிவோம், அது நல்லதல்ல.

எனவே, இதை தீர்க்க நாம் மற்றொரு அணுகுமுறையைப் பற்றி சிந்திக்க வேண்டும். பிறகு டைனமிக் நிரலாக்க எங்கள் மீட்புக்கு வருகிறது. ஏனென்றால், பாதைகளை உருவாக்குவதற்குப் பதிலாக, ஒரு கலத்திலிருந்து அடையக்கூடிய அதிகபட்சம் என்ன என்பதை எப்படியாவது தெரிந்து கொள்ள முடிந்தால், கீழ் வரிசையை அடையலாம். அந்த வழியில் நாம் அதற்கு அருகிலுள்ள ஆனால் அதற்கு மேலே உள்ள கலத்திற்கான முடிவைப் பெறலாம். எனவே, சிறிய துணை சிக்கல்களை தீர்க்க டி.பியைப் பயன்படுத்துகிறோம். அந்த துணை சிக்கல்களுக்கான முடிவுகளை இணைப்பதன் மூலம் அசல் சிக்கலுக்கான பதில்களைக் காணலாம்.

முதலில், கடைசி வரிசையில் உள்ள கலங்களுக்கான பதிலை நிரப்புகிறோம். கீழ் வரிசையில் உள்ள கலங்களிலிருந்து தொடங்கினால் அடையக்கூடிய அதிகபட்ச தொகை எண் என்பது எங்களுக்குத் தெரியும். அதன் பிறகு, நாங்கள் கீழ் வரிசையின் மேலே உள்ள வரிசைக்கு செல்கிறோம். தற்போதைய வரிசையில் உள்ள ஒவ்வொரு கலத்திற்கும், அதற்குக் கீழே உள்ள வரிசையில் உள்ள கலங்களின் டிபி மதிப்புகளை நாம் தேர்வு செய்யலாம். இந்த வழியில் நாம் மேல்நோக்கி செல்கிறோம். நாங்கள் மேல் வரிசையை அடையும்போது, ​​நாங்கள் சிக்கலைச் செய்துள்ளோம்.

ஒரு முக்கோணத்தில் அதிகபட்ச பாதை தொகையைக் கண்டுபிடிக்க சி ++ குறியீடு

#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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என் ^ 2), ஒவ்வொரு வரிசையிலும் ஒவ்வொரு நெடுவரிசையிலும் நாங்கள் நகர்ந்தோம். செயல்பாட்டில், நாங்கள் ஒவ்வொரு கலத்திற்கும் பயணித்தோம். முக்கோணத்தில் O (N ^ 2) செல்கள் இருந்ததால், DP க்கான மாற்றம் O (1) செயல்பாட்டை மட்டுமே எடுத்தது. எனவே, நேர சிக்கலானது பல்லுறுப்புக்கோவையாகும்.

விண்வெளி சிக்கலானது

ஓ (என் ^ 2) நாங்கள் 2D டிபி வரிசையை உருவாக்கியதால். இதனால் விண்வெளி சிக்கலானது பல்லுறுப்புக்கோவையாகும்.