උපරිම සාමාන්‍ය අගය සහිත මාර්ගය


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ සිස්කෝ එපික් පද්ධති ග්‍රේ ඔරේන්ජ් 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 වෙත යාම හෝ කාල සීමාව ඉක්මවා යනු ඇත. මන්ද එවැනි මාර්ග ජනනය කිරීම on ාතීය කාල සංකීර්ණතාවයට හේතු වනු ඇත. එබැවින්, කාල සීමාවන් යටතේ ගැටළුව විසඳීම. අපි කාර්යක්ෂම විසඳුමක් සොයා ගත යුතුයි. නමුත්, අපට එය කළ හැක්කේ කෙසේද? අපට එය ගතික ක්‍රමලේඛනය භාවිතයෙන් කළ හැකිය. තවද ගැටළුව උපරිම මාර්ග එකතුවට බොහෝ සෙයින් සමාන වේ. එම ගැටලුවේදී, අපි 2D අරාවකින් උපරිම මාර්ග එකතුව සොයාගත යුතුය. අපි කරන්න යන දේමයි, නමුත් අවසානයේදී අපි සාමාන්‍යය ගන්නෙමු.

ඒ නිසා ගතික වැඩසටහන්කරණය ප්රවේශය. අපි 2D ඩීපී අරාවක් සාදන්නෙමු, එහිදී ඩීපී මෙට්‍රික් හි සෑම සෛලයකම ඉහළ වම්පස කෙළවරේ සිට වත්මන් කොටුව දක්වා ආරම්භ කිරීමට අවශ්‍ය නම් ලබා ගත හැකි උපරිම මුදල දක්වනු ඇත. එබැවින් අපට සාමාන්‍ය පුනරාවර්තන සම්බන්ධතාවයක් ලිවිය හැකිය.

// මූලික නඩු
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] // අනෙකුත් සියලුම සෛල සඳහා

උපරිම සාමාන්‍ය අගය සහිත මාර්ගය සඳහා C ++ කේතය

#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 DP අරාවක් නිර්මාණය කළ නිසා.