Ոսկու հանքի խնդիր


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Flipkart Google Microsoft PayU Uber
Դասավորություն Դինամիկ ծրագրավորում Matrix

Խնդիրի հայտարարություն

«Ոսկու հանքի խնդիրը» նշում է, որ ձեզ տրվում է 2D Ցանց ունենալով որոշ ոչ-բացասական մետաղադրամներ, որոնք տեղադրված են տվյալ ցանցի յուրաքանչյուր խցում: Սկզբնապես, հանքագործը կանգնած է առաջին սյունակում, բայց շարքում սահմանափակում չկա: Նա կարող է սկսել ցանկացած շարքում: Հանքագործը կարող է շարժվել միայն ճիշտ ուղղությամբ դեպի հաջորդ հաջորդ սյունը: Նա կարող է շարժվել նաև անկյունագծերով: Այսպիսով, յուրաքանչյուր բջիջից դուք ունեք երեք ուղղություն ՝ աջից, վերևից աջ կամ ներքևից աջ: Բայց բջիջը պետք է լինի ցանցի սահմանի ներսում: Դուք պետք է գտնեք, թե ո՞րն է առավելագույն քանակությամբ ոսկի, որը նա կարող է հավաքել:

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

Բացատրություն. Տեսեք ուղու պատկերը, հանքագործը պետք է ընտրի 150 ոսկի հավաքելու համար:

Ոսկու հանքի խնդիր

Ոսկու հանքի խնդրի մոտեցում

Միամիտ մոտեցում կարող է լինել հետընթացի օգտագործումը `բոլոր այն ուղիները արտադրելու համար, որոնք հանքափորը կարող է անցնել առաջին սյունակից մինչև վերջին սյուն: Եվ յուրաքանչյուր արահետի համար հաշվարկեք յուրաքանչյուր ուղու վրա հավաքված ոսկե մետաղադրամների քանակը: Բայց այս մոտեցումը ժամանակատար է և կանցնի ժամանակի սահմանը, քանի որ մենք մեծացնում ենք ցանցի չափը:

Ավելի լավ մոտեցում կլինի մեզ համար հայտնի որոշ փաստերի օգտագործումը: Մենք գիտենք, որ miner- ը ներկայիս բջիջ կարող է գալ միայն երեք բջիջներից. Այն բջիջը, որը գտնվում է ընթացիկ բջջի հենց ձախ կողմում, այս ձախ խցից վերևում գտնվող բջիջը և այս ձախ խցի ներքևում գտնվող բջիջը: Այսպիսով, մենք կարող ենք վերցնել առավելագույնը այս երեք արժեքներից `մեզ կտան առավելագույն մետաղադրամներ, որոնք կարող են հավաքվել, եթե մենք գտնվում ենք ներկայիս խցում: Այսպիսով, մենք կօգտագործենք դինամիկ ծրագրավորում արդյունքը պահելու համար ցանկացած ընթացիկ բջիջի համար: Դա առավելագույն թվով մետաղադրամներ է, որոնք կարող են հավաքվել, եթե հանքափորը գա ներկայիս խուց:

Կոդ

Ոսկե հանքի խնդրի համար 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

Java կոդ ՝ Gold Mine խնդրի համար

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

Բարդության վերլուծություն

Timeամանակի բարդություն

O (N * M), պատճառը, որ մենք ստիպված էինք անցնել ամբողջ ցանցով: Եվ քանի որ այն ունի N * M բջիջներ: Timeամանակի բարդությունը բազմանդամ է:

Տիեզերական բարդություն

Ո (1), քանի որ մենք օգտագործել ենք նախնական մատրիցը դրա վրա աշխատելու համար: Մենք չենք օգտագործել որևէ լրացուցիչ մատրիցա / ցանց `միջանկյալ արդյունքները պահելու համար: Բայց ծրագիրը, որպես ամբողջություն, պահանջում է O (N * M) տիեզերական բարդություն: