ಗರಿಷ್ಠ ಸರಾಸರಿ ಮೌಲ್ಯದೊಂದಿಗೆ ಹಾದಿ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಸಿಸ್ಕೋ ಎಪಿಕ್ ಸಿಸ್ಟಮ್ಸ್ ಗ್ರೇ ಆರೆಂಜ್ ಎಸ್‌ಎಪಿ ಲ್ಯಾಬ್‌ಗಳು ಟೈಮ್ಸ್ ಇಂಟರ್ನೆಟ್
ಅರೇ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ  

“ಗರಿಷ್ಠ ಸರಾಸರಿ ಮೌಲ್ಯದೊಂದಿಗೆ ಹಾದಿ” ಸಮಸ್ಯೆ ನಿಮಗೆ 2 ಡಿ ಅರೇ ಅಥವಾ ಪೂರ್ಣಾಂಕಗಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಈಗ ನೀವು ಮೇಲಿನ ಎಡ ಕೋಶದಲ್ಲಿ ನಿಂತಿದ್ದೀರಿ ಎಂದು ಪರಿಗಣಿಸಿ ಮತ್ತು ಕೆಳಗಿನ ಬಲಕ್ಕೆ ತಲುಪಬೇಕು. ಗಮ್ಯಸ್ಥಾನವನ್ನು ತಲುಪಲು, ನೀವು ಕೆಳಗಿನ ದಿಕ್ಕಿನಲ್ಲಿ ಅಥವಾ ಸರಿಯಾದ ದಿಕ್ಕಿನಲ್ಲಿ ಚಲಿಸಬೇಕಾಗುತ್ತದೆ. ಗಮ್ಯಸ್ಥಾನದ ಪ್ರಕಾರ, ಇಲ್ಲಿ ನಾವು ಕೆಳಗಿನ ಬಲ ಕೋಶವನ್ನು ಅರ್ಥೈಸುತ್ತೇವೆ. ಒಂದು ಷರತ್ತು ಇದೆ, ನೀವು ಅಂತಹ ಹಾದಿಯಲ್ಲಿ ಸಾಗಬೇಕಾದರೆ ಅದು ನಮಗೆ ಗರಿಷ್ಠ ಸರಾಸರಿ ಮೌಲ್ಯವನ್ನು ನೀಡುತ್ತದೆ.

ಉದಾಹರಣೆ  

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] = a [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) ನಾವು 2 ಡಿ ಡಿಪಿ ರಚನೆಯನ್ನು ರಚಿಸಿದ್ದರಿಂದ.