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


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது Citrix டி.இ ஷா டைரக்டி Expedia
டைனமிக் புரோகிராமிங் கணித

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

உதாரணமாக  

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

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

விளக்கம்

மேலிருந்து கீழாக நகர்த்துவதன் மூலம் அடையக்கூடிய அதிகபட்ச தொகை 15. இது பின்வரும் படிகளிலிருந்து அடையப்படலாம்: 1 -> 2 -> 12. இதை மேலே உள்ள படத்திலிருந்து நன்கு புரிந்து கொள்ள முடியும்.

அணுகுமுறை  

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

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

மேலும் காண்க
ஒரு வரிசையில் அருகிலுள்ள கூறுகளை வேறுபடுத்துங்கள்

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

குறியீடு  

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

#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), ஏனெனில் டிபி அட்டவணைக்கு அதே உள்ளீட்டு வரிசையைப் பயன்படுத்துகிறோம். புதிய டிபி வரிசையை உருவாக்குவதற்கான இடத்தை நாங்கள் எடுக்கவில்லை என்பதால் விண்வெளி சிக்கலானது நிலையானது.