ปัญหาเหมืองทอง  


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน Flipkart Google ไมโครซอฟท์ payu Uber
แถว การเขียนโปรแกรมแบบไดนามิก มดลูก

คำชี้แจงปัญหา  

"ปัญหาเหมืองทองคำ" ระบุว่าคุณได้รับ 2 มิติ ตะแกรง มีเหรียญที่ไม่ติดลบอยู่ในแต่ละเซลล์ของตารางที่กำหนด ในขั้นต้นคนงานเหมืองจะยืนอยู่ที่คอลัมน์แรก แต่ไม่มีข้อ จำกัด ในแถว เขาสามารถเริ่มต้นในแถวใดก็ได้ คนงานเหมืองสามารถเคลื่อนที่ไปในทิศทางที่ถูกต้องไปยังคอลัมน์ถัดไปเท่านั้น เขายังสามารถเคลื่อนไหวในแนวทแยงมุม ดังนั้นจากแต่ละเซลล์คุณมีสามทิศทางเพียงไปทางขวาบนขวาหรือขวาล่าง แต่เซลล์ควรอยู่ภายในขอบเขตของเส้นตาราง คุณต้องหาจำนวนเหรียญทองสูงสุดที่เขาสามารถเก็บได้?

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

คำอธิบาย: ดูภาพสำหรับเส้นทางนักขุดควรเลือกเพื่อรวบรวม 150 เหรียญทอง

ปัญหาเหมืองทอง  

แนวทางแก้ไขปัญหาเหมืองทองคำ  

วิธีการที่ไร้เดียงสาสามารถใช้การย้อนรอยเพื่อสร้างเส้นทางทั้งหมดที่นักขุดสามารถใช้ตั้งแต่คอลัมน์แรกไปจนถึงคอลัมน์สุดท้าย และสำหรับแต่ละเส้นทางจะคำนวณจำนวนเหรียญทองที่เก็บได้ในแต่ละเส้นทาง แต่วิธีนี้ใช้เวลานานและจะเกินเวลาที่กำหนดเมื่อเราเพิ่มขนาดของเส้นตาราง

แนวทางที่ดีกว่าคือการใช้ข้อเท็จจริงบางอย่างที่เราทราบกันดี เรารู้ว่าคนงานเหมืองสามารถมาที่เซลล์ปัจจุบันได้จากเซลล์สามเซลล์เท่านั้นเซลล์ที่อยู่ทางซ้ายของเซลล์ปัจจุบันเซลล์ที่อยู่เหนือเซลล์ด้านซ้ายนี้และเซลล์ที่อยู่ด้านล่างของเซลล์ด้านซ้ายนี้ ดังนั้นเราสามารถใช้ค่าสูงสุดของทั้งสามค่านี้จะทำให้เราได้เหรียญสูงสุดที่สามารถรวบรวมได้หากเราอยู่ที่เซลล์ปัจจุบัน ดังนั้นเราจะใช้ การเขียนโปรแกรมแบบไดนามิก เพื่อจัดเก็บผลลัพธ์สำหรับเซลล์ปัจจุบัน นั่นคือจำนวนเหรียญสูงสุดที่สามารถรวบรวมได้หากคนขุดแร่มาที่เซลล์ปัจจุบัน

ดูสิ่งนี้ด้วย
ผลรวมเส้นทางสูงสุดในรูปสามเหลี่ยม

รหัส  

รหัส 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)