அதிகபட்ச சராசரி மதிப்புடன் பாதை


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது சிஸ்கோ காவிய அமைப்புகள் கிரே ஆரஞ்சு SAP ஆய்வகங்கள் டைம்ஸ் இணையம்
அணி டைனமிக் புரோகிராமிங் மேட்ரிக்ஸ்

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

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

உதாரணமாக

3 3 // number of rows and columns
1 1 2
10 1 100
10 10 1
22.6

விளக்கம்

அதிகபட்ச சராசரி மதிப்புடன் பாதை

1-> 10-> 1-> 100-> 1. எனவே இதைச் சேர்ப்பது மொத்தம் 113 தொகையைத் தருகிறது. இதனால் சராசரி 113/5 = 22.6 க்கு சமமாகிறது

அணுகுமுறை

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

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

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

// அடிப்படை வழக்குகள்
dp [0] [0] = அ [0] [0]
dp [i] [0] = dp [i-1] [0] + a [i] [0] // இங்கே நான் 1 வது வரிசையில் இருந்து மேட்ரிக்ஸின் கடைசி வரிசை வரை தொடங்குகிறேன்
dp [0] [i] = dp [0] [i-1] + a [0] [i] // இங்கே நான் 1 வது நெடுவரிசையில் இருந்து மேட்ரிக்ஸின் கடைசி நெடுவரிசை வரை தொடங்குகிறேன்
// மறுநிகழ்வு உறவு
dp [i] [j] = அதிகபட்சம் (dp [i-1] [j], dp [i] [j-1]) + a [i] [j] // மற்ற எல்லா கலங்களுக்கும்

அதிகபட்ச சராசரி மதிப்புடன் பாதைக்கான சி ++ குறியீடு

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int n,m; // number of rows and columns in input matrix
  cin>>n>>m;

  int input[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)
      cin>>input[i][j];
  }

  int dp[n][m];
  dp[0][0] = input[0][0];
  for(int i=1;i<n;i++)
    dp[i][0] = dp[i-1][0] + input[i][0];
  for(int i=1;i<m;i++)
    dp[0][i] = dp[0][i-1] + input[0][i];

  for(int i=1;i<n;i++){
    for(int j=1;j<m;j++)
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + input[i][j];
  }

  // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
  cout<<(dp[n-1][m-1]/((double)n+m-1));
}
3 3
1 1 2
10 1 100
10 10 1
22.6

அதிகபட்ச சராசரி மதிப்புடன் பாதைக்கான ஜாவா குறியீடு

import java.util.*;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(); int m = sc.nextInt(); // number of rows and columns in input matrix

    int input[][] = new int[n][m];
    for(int i=0;i<n;i++){
      for(int j=0;j<m;j++)
        input[i][j] = sc.nextInt();
    }

    int dp[][] = new int[n][m];
    dp[0][0] = input[0][0];
    for(int i=1;i<n;i++)
      dp[i][0] = dp[i-1][0] + input[i][0];
    for(int i=1;i<m;i++)
      dp[0][i] = dp[0][i-1] + input[0][i];

    for(int i=1;i<n;i++){
      for(int j=1;j<m;j++)
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + input[i][j];
    }

    // division by n+m-1, because you need to travel at least n+m-1 cells to reach bottom right cell
    System.out.print(dp[n-1][m-1]/((double)n+m-1));
  }
}
3 3
1 1 2
10 1 100
10 10 1
22.6

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

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

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

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

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