Проблема золотого рудника


Рівень складності Medium
Часто запитують у Амазонка Flipkart Google Microsoft PayU Убер
масив Динамічне програмування Матриця

Постановка проблеми

У "Проблемі золотого рудника" зазначено, що вам дають 2D сітка маючи кілька негативних монет, поміщених у кожну клітинку даної сітки. Спочатку майнер стоїть у першій колонці, але для рядка немає обмежень. Він може стартувати в будь-якому ряду. Майнер може рухатися лише в правильному напрямку до наступної наступної колонки. Він також може рухатися по діагоналях. Отже, від кожної клітинки у вас є три напрямки, праворуч, праворуч або знизу праворуч. Але комірка повинна знаходитися всередині меж сітки. Вам потрібно знайти, яку максимальну кількість золотих монет він може зібрати?

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

Пояснення: Дивіться зображення шляху, майнер повинен вибрати для збору 150 золотих монет.

Проблема золотого рудника

Підхід до проблеми золотих копалень

Наївним підходом може бути використання зворотного відстеження для створення всіх шляхів, які майнер може пройти від першого стовпця до останнього. І для кожного шляху обчисліть кількість золотих монет, зібраних на кожному шляху. Але такий підхід трудомісткий і перевищуватиме обмеження за часом, оскільки ми збільшуємо розмір сітки.

Кращим підходом буде використання деяких відомих нам фактів. Ми знаємо, що майнер може прийти до поточної комірки лише з трьох клітин, клітини, яка знаходиться зліва від поточної комірки, комірки, яка знаходиться трохи вище цієї лівої комірки, і комірки, яка знаходиться внизу цієї лівої комірки. Отже, ми можемо взяти максимум з цих трьох значень, і це дасть нам максимум монет, які можна зібрати, якщо ми знаходимось у поточній комірці. Отже, ми будемо використовувати динамічне програмування щоб зберегти результат для будь-якої поточної комірки. Це максимальна кількість монет, яку можна зібрати, якщо майнер дійде до поточної комірки.

код

Код С ++ для проблеми Gold Mine

#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

Аналіз складності

Складність часу

O (N * M), тому що нам довелося пройти всю сітку. А оскільки він має N * M клітини. Складність часу поліноміальна.

Складність простору

O (1), оскільки ми працювали над початковою матрицею. Ми не використовували жодної додаткової матриці / сітки для зберігання проміжних результатів. Але програма в цілому вимагає складності простору O (N * M).