सुन खानीको समस्या


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन फ्लिपकार्ट गुगल माइक्रोसफ्ट PayU Uber
एरे डायनामिक प्रोग्रामिंग म्याट्रिक्स

समस्या वक्तव्य

"गोल्ड माइन समस्या" ले भन्छ कि तपाईंलाई एक २ डी दिइन्छ ग्रिड दिइएका ग्रिडको प्रत्येक सेलमा केही गैर-नकारात्मक सिक्का राखिएको छ। प्रारम्भमा, माइनर पहिलो स्तम्भमा उभिरहेको छ तर प the्क्तिमा प्रतिबन्ध छैन। ऊ कुनै प row्क्तिमा सुरू गर्न सक्दछ। माइनर केवल सहि दिशामा मात्र अर्को स्तम्भमा जान सक्छ। ऊ विकर्णमा पनि सार्न सक्छ। त्यसैले प्रत्येक सेलबाट तपाईसँग तीन दिशा निर्देशनहरू छन्, मात्र दायाँ, माथी दायाँ, वा तल दायाँ। तर सेल ग्रिडको सीमा भित्र हुनु पर्छ। तपाईंले स coins्कलन गर्न सक्ने अधिकतम सुनको सिक्का के खोज्नु पर्छ?

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

स्पष्टीकरण: मार्गको लागि छवि हेर्नुहोस्, खानीले १ 150० सुनको सिक्का स for्कलनका लागि छनौट गर्नुपर्छ।

सुन खानीको समस्या

सुन खानी समस्या को लागी दृष्टिकोण

एक भोकाउने दृष्टिकोण ब्याट्र्याकिंग प्रयोग गरी सबै बाटोहरू उत्पादन गर्न सक्दछ जुन एक माइनरले पहिलो स्तम्भबाट अन्तिम स्तम्भमा लिन सक्दछ। र प्रत्येक मार्गको लागि प्रत्येक पथमा संकलन गरिएको सुनका सिक्काहरूको संख्याको हिसाब गर्नुहोस्। तर यो दृष्टिकोण समय खपत हुने र समय सीमा नाघ्ने गरी हामी ग्रिडको आकार बढाउनेछौं।

राम्रो दृष्टिकोण केहि तथ्यहरू जुन हामीलाई थाहा छ प्रयोग गर्नका लागि हुनेछ। हामीलाई थाहा छ कि खानी मानेको सेलमा केवल तीन सेलहरू आउन सक्छ, सेल जुन हालको सेलको बायाँ तर्फ छ, सेल जुन यो बायाँ सेलको माथि छ, र सेल जुन यो बायाँ सेलको तल मात्र छ। त्यसैले हामी यी तीन मानहरूको अधिकतम लिन सक्दछौं हामीलाई अधिकतम सिक्का दिन्छ जुन हामी हालको सेलमा छौं भने स collected्कलन गर्न सकिन्छ। त्यसो भए हामी प्रयोग गर्नेछौं गतिशील प्रोग्रामिंग कुनै पनि हालको सेलको लागि नतिजा भण्डारण गर्न। त्यो सिक्काको अधिकतम संख्या हो जुन स collected्कलन गर्न सकिन्छ यदि खानीको हालको सेलमा आयो।

कोड

C ++ गोल्ड माईन समस्याको लागि कोड

#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

जटिलता विश्लेषण

समय जटिलता

O (N * M), कारण हामी सबै ग्रिड को माध्यम बाट पार गर्नु थियो। र किनकि यसमा N * M सेलहरू छन्। समय जटिलता बहुपद हो।

ठाउँ जटिलता

O (१), किनकि हामीले सुरुमा म्याट्रिक्स प्रयोग गरीरहेका छौं। मध्यवर्ती नतिजा भण्डार गर्न हामीले कुनै पनि अतिरिक्त म्याट्रिक्स / ग्रिड प्रयोग गरेनौं। तर पूरै कार्यक्रममा O (N * M) ठाउँ जटिलता आवश्यक छ।