ಚಿನ್ನದ ಗಣಿ ಸಮಸ್ಯೆ  


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಫ್ಲಿಪ್ಕಾರ್ಟ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಪೇಯು ಉಬರ್
ಅರೇ ಡೈನಾಮಿಕ್ ಪ್ರೊಗ್ರಾಮಿಂಗ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್

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

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

matrix = {{10, 20, 0},
          {30, 10, 100},
          {10, 10, 10}}
The maximum coins he can collect = 150

ವಿವರಣೆ: ಮಾರ್ಗಕ್ಕಾಗಿ ಚಿತ್ರವನ್ನು ನೋಡಿ, ಗಣಿಗಾರ 150 ಚಿನ್ನದ ನಾಣ್ಯಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ಆರಿಸಿಕೊಳ್ಳಬೇಕು.

ಚಿನ್ನದ ಗಣಿ ಸಮಸ್ಯೆಪಿನ್  

ಚಿನ್ನದ ಗಣಿ ಸಮಸ್ಯೆಗೆ ಅನುಸಂಧಾನ  

ಗಣಿಗಾರನು ಮೊದಲ ಕಾಲಮ್‌ನಿಂದ ಕೊನೆಯ ಕಾಲಮ್‌ಗೆ ತೆಗೆದುಕೊಳ್ಳಬಹುದಾದ ಎಲ್ಲಾ ಮಾರ್ಗಗಳನ್ನು ಉತ್ಪಾದಿಸಲು ಬ್ಯಾಕ್‌ಟ್ರಾಕಿಂಗ್ ಅನ್ನು ಬಳಸುವುದು ಒಂದು ನಿಷ್ಕಪಟ ವಿಧಾನವಾಗಿದೆ. ಮತ್ತು ಪ್ರತಿ ಹಾದಿಗೆ ಪ್ರತಿ ಹಾದಿಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿದ ಚಿನ್ನದ ನಾಣ್ಯಗಳ ಸಂಖ್ಯೆಯನ್ನು ಲೆಕ್ಕಹಾಕಿ. ಆದರೆ ಈ ವಿಧಾನವು ಸಮಯ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ನಾವು ಗ್ರಿಡ್‌ನ ಗಾತ್ರವನ್ನು ಹೆಚ್ಚಿಸುವುದರಿಂದ ಸಮಯದ ಮಿತಿಯನ್ನು ಮೀರುತ್ತದೆ.

ಸಹ ನೋಡಿ
ತ್ರಿಕೋನದಲ್ಲಿ ಗರಿಷ್ಠ ಮಾರ್ಗ ಮೊತ್ತ

ನಮಗೆ ತಿಳಿದಿರುವ ಕೆಲವು ಸಂಗತಿಗಳನ್ನು ಬಳಸುವುದು ಉತ್ತಮ ವಿಧಾನವಾಗಿದೆ. ಗಣಿಗಾರನು ಪ್ರಸ್ತುತ ಕೋಶಕ್ಕೆ ಮೂರು ಕೋಶಗಳಿಂದ ಮಾತ್ರ ಬರಬಹುದು ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ, ಪ್ರಸ್ತುತ ಕೋಶದ ಎಡಭಾಗದಲ್ಲಿರುವ ಕೋಶ, ಈ ಎಡ ಕೋಶದ ಮೇಲಿರುವ ಕೋಶ ಮತ್ತು ಈ ಎಡ ಕೋಶದ ಕೆಳಭಾಗದಲ್ಲಿರುವ ಕೋಶ. ಆದ್ದರಿಂದ ನಾವು ಈ ಮೂರು ಮೌಲ್ಯಗಳ ಗರಿಷ್ಠವನ್ನು ತೆಗೆದುಕೊಳ್ಳಬಹುದು ನಾವು ಪ್ರಸ್ತುತ ಕೋಶದಲ್ಲಿದ್ದರೆ ಸಂಗ್ರಹಿಸಬಹುದಾದ ಗರಿಷ್ಠ ನಾಣ್ಯಗಳನ್ನು ನೀಡುತ್ತದೆ. ಆದ್ದರಿಂದ, ನಾವು ಬಳಸುತ್ತೇವೆ ಡೈನಾಮಿಕ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಯಾವುದೇ ಪ್ರಸ್ತುತ ಕೋಶಕ್ಕಾಗಿ ಫಲಿತಾಂಶವನ್ನು ಸಂಗ್ರಹಿಸಲು. ಗಣಿಗಾರನು ಪ್ರಸ್ತುತ ಕೋಶಕ್ಕೆ ಬಂದರೆ ಸಂಗ್ರಹಿಸಬಹುದಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ನಾಣ್ಯಗಳು ಅದು.

ಕೋಡ್  

ಗೋಲ್ಡ್ ಮೈನ್ ಸಮಸ್ಯೆಗೆ ಸಿ ++ ಕೋಡ್

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


int main()
{
    // grid size n*m
    int n,m;cin>>n>>m;
    int a[n][m]; // grid storing the number of gold coins in each cell
    // taking input of the grid storing the number of gold coins
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cin>>a[i][j];
    }

    /*
    
    ^  ^  ^
     \
    ^- &  ^
     /
    ^  ^  ^
    Consider this represents a grid and we are currently at a cell having & stored in it.
    So only there are three cells from which miner could have reached current cell
    So we take maximum of all the options and thus at the end in the last corner
    We receive the largest amount of gold coins.
    */
    for(int j=1;j<m;j++){
        for(int i=0;i<n;i++)
            a[i][j] += max({((i>0) ? a[i-1][j-1] : 0), a[i][j-1], ((i+1<n) ? a[i+1][j-1] : 0)});
    }

    int ans = 0;
    for(int i=0;i<n;i++){
        ans = max(ans, a[i][m-1]);
    }
    cout<<ans<<endl;
}
3 3
10 20 0
30 10 100
10 10 10
150

ಗೋಲ್ಡ್ ಮೈನ್ ಸಮಸ್ಯೆಗೆ ಜಾವಾ ಕೋಡ್

import java.util.*;

class Main{
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();// grid size n*m
    	int m = sc.nextInt();
      int a[][] = new int[n][m]; // grid storing the number of gold coins in each cell
      // taking input of the grid storing the number of gold coins
      for(int i=0;i<n;i++){
          for(int j=0;j<m;j++)
              a[i][j] = sc.nextInt();
      }

      /*
      
      ^  ^  ^
       \
      ^- &  ^
       /
      ^  ^  ^
      Consider this represents a grid and we are currently at a cell having & stored in it.
      So only there are three cells from which miner could have reached current cell
      So we take maximum of all the options and thus at the end in the last corner
      We receive the largest amount of gold coins.
      */
      for(int j=1;j<m;j++){
          for(int i=0;i<n;i++){
          	int topLeft = ((i>0) ? a[i-1][j-1] : 0);
          	int justLeft = a[i][j-1];
          	int bottomLeft = ((i+1<n) ? a[i+1][j-1] : 0);
              int maxOfAll = Math.max(topLeft, bottomLeft);
              maxOfAll = Math.max(maxOfAll, justLeft);
              a[i][j] += maxOfAll;
          }
      }

      int ans = 0;
      for(int i=0;i<n;i++){
          ans = Math.max(ans, a[i][m-1]);
      }
    System.out.println(ans);
  }
}
3 3
10 20 0
30 10 100
10 10 10
150

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ  

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎಂ), ನಾವು ಎಲ್ಲಾ ಗ್ರಿಡ್ ಮೂಲಕ ಸಂಚರಿಸಬೇಕಾಗಿತ್ತು. ಮತ್ತು ಇದು N * M ಕೋಶಗಳನ್ನು ಹೊಂದಿರುವುದರಿಂದ. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಬಹುಪದೀಯವಾಗಿದೆ.

ಸಹ ನೋಡಿ
ರೋಮನ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಪೂರ್ಣಾಂಕ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1), ನಾವು ಕೆಲಸ ಮಾಡಲು ಆರಂಭಿಕ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಬಳಸಿದ್ದೇವೆ. ಮಧ್ಯಂತರ ಫಲಿತಾಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ / ಗ್ರಿಡ್ ಅನ್ನು ಬಳಸಲಿಲ್ಲ. ಆದರೆ ಒಟ್ಟಾರೆಯಾಗಿ ಪ್ರೋಗ್ರಾಂಗೆ O (N * M) ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಯ ಅಗತ್ಯವಿದೆ.