Алтны уурхайн асуудал  


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Flipkart Google-ийн Microsoft- PayU Uber
Array Динамик програмчлал матриц

Асуудлын мэдэгдэл  

“Алтны уурхайн асуудал” дээр танд 2 хэмжээст хэмжээ өгдөг гэсэн сүлжээ тухайн сүлжээний нүд бүрт сөрөг биш зоос байрлуулсан байх. Эхэндээ олборлогч эхний баганад зогсож байгаа боловч эгнээнд хязгаарлалт байхгүй байна. Тэрээр аль ч эгнээнд эхэлж болно. Олборлогч зөвхөн зөв чиглэлд дараагийн багана руу шилжиж болно. Тэрбээр диагональ хэлбэрээр хөдөлж чаддаг. Тиймээс нүд тус бүрээс танд баруун, баруун дээд, баруун доод гэсэн гурван чиглэл байна. Гэхдээ нүд нь сүлжээний хил дотор байх ёстой. Түүний цуглуулж чадах хамгийн дээд хэмжээ нь хэдэн алтан зоос болохыг олох хэрэгтэй байна уу?

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

Тайлбар: Уурхайчин 150 алтан зоос цуглуулахаар сонгох ёстой замын зургийг үзнэ үү.

Алтны уурхайн асуудалPin  

Алтны уурхайн асуудалд хандах хандлага  

Уурхайчин эхний баганаас сүүлчийн багана хүртэлх бүх замыг гаргаж авахын тулд буцах мөрийг ашиглах нь гэнэн хандлага байж болно. Зам тус бүр дээр цуглуулсан алтан зоосны тоог тооцоол. Гэхдээ энэ арга нь цаг хугацаа их шаарддаг бөгөөд сүлжээний хэмжээг нэмэгдүүлэхэд цаг хугацааны хязгаараас хэтрэх болно.

мөн үзнэ үү
Гурвалжин дахь хамгийн их замын нийлбэр

Бидний мэддэг зарим баримтыг ашиглах нь илүү сайн арга юм. Олборлогч одоогийн нүдэнд зөвхөн гурван нүднээс, одоогийн нүдний зүүн талд байгаа, энэ зүүн нүдний дөнгөж дээр байрлах нүд ба энэ зүүн нүдний яг доод хэсэгт байрлах нүднээс л орж ирж болно гэдгийг бид мэднэ. Тиймээс бид эдгээр гурван утгын дээд хэмжээг авах боломжтой бөгөөд хэрэв бид одоогийн нүдэнд байгаа бол цуглуулж болох хамгийн их зоосыг өгөх болно. Тиймээс бид ашиглах болно динамик програмчлал үр дүнг одоогийн нүдэнд хадгалах. Энэ нь олборлогч одоогийн нүдэнд ирвэл цуглуулж болох зоосны дээд хэмжээ юм.

код  

Алтны уурхайн асуудалд зориулсан 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 код

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 эсүүдтэй тул. Цаг хугацааны нарийн төвөгтэй байдал нь олон гишүүнт юм.

мөн үзнэ үү
Ромын Leetcode шийдлийн бүхэл тоо

Сансрын нарийн төвөгтэй байдал

O (1), бид эхний матрицыг ашиглахдаа ашигласан тул. Бид завсрын үр дүнг хадгалахын тулд нэмэлт матриц / тор ашиглаагүй. Гэхдээ програмыг бүхэлд нь O (N * M) сансрын нарийн төвөгтэй байдлыг шаарддаг.