ບັນຫາແຮ່ທາດ ຄຳ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon Flipkart ກູໂກ Microsoft PayU Uber
Array ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ມາຕຣິກເບື້ອງ

ຖະແຫຼງການບັນຫາ

ບັນຫາກ່ຽວກັບແຮ່ທາດ ຄຳ ລະບຸວ່າທ່ານໄດ້ຮັບ 2D ຕາຂ່າຍໄຟຟ້າ ມີບາງຫຼຽນທີ່ບໍ່ລົບກວນວາງຢູ່ໃນແຕ່ລະຫ້ອງຂອງຕາຂ່າຍໄຟຟ້າທີ່ໃຫ້. ໃນເບື້ອງຕົ້ນ, ຜູ້ແຮ່ທາດແມ່ນຢືນຢູ່ຖັນ ທຳ ອິດແຕ່ບໍ່ມີຂໍ້ ຈຳ ກັດຢູ່ແຖວ. ລາວສາມາດເລີ່ມຕົ້ນໃນແຖວໃດໆ. ຜູ້ແຮ່ທາດສາມາດຍ້າຍໄປໃນທິດທາງທີ່ຖືກຕ້ອງໄປຫາຖັນຕໍ່ໄປ. ລາວຍັງສາມາດຍ້າຍໃນເສັ້ນຂວາງ. ສະນັ້ນຈາກແຕ່ລະຫ້ອງ, ທ່ານມີສາມທິດທາງ, ພຽງແຕ່ໄປທາງຂວາ, ຂວາເທິງ, ດ້ານຂວາລຸ່ມ. ແຕ່ຫ້ອງຄວນຢູ່ໃນຂອບເຂດຂອງຕາຂ່າຍໄຟຟ້າ. ທ່ານ ຈຳ ເປັນຕ້ອງຊອກຫາ ຄຳ ທີ່ມີ ຈຳ ນວນສູງສຸດທີ່ລາວສາມາດເກັບມາໄດ້?

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

ຄຳ ອະທິບາຍ: ເບິ່ງຮູບພາບ ສຳ ລັບເສັ້ນທາງ, ຜູ້ແຮ່ທາດຄວນເລືອກ ສຳ ລັບການເກັບ 150 ຫຼຽນ ຄຳ.

ບັນຫາແຮ່ທາດ ຄຳ

ວິທີການແກ້ໄຂບັນຫາແຮ່ທາດ ຄຳ

ວິທີການທີ່ໂງ່ຈ້າສາມາດເປັນການໃຊ້ backtracking ເພື່ອຜະລິດທຸກໆເສັ້ນທາງທີ່ນັກແຮ່ທາດສາມາດໃຊ້ໄດ້ຈາກຖັນ ທຳ ອິດຈົນເຖິງຖັນສຸດທ້າຍ. ແລະ ສຳ ລັບແຕ່ລະເສັ້ນທາງຄິດໄລ່ ຈຳ ນວນຫຼຽນ ຄຳ ທີ່ເກັບໃນແຕ່ລະເສັ້ນທາງ. ແຕ່ວິທີການນີ້ແມ່ນໃຊ້ເວລາແລະຈະເກີນ ກຳ ນົດເວລາເພາະວ່າພວກເຮົາເພີ່ມຂະ ໜາດ ຂອງຕາຂ່າຍໄຟຟ້າ.

ວິທີການທີ່ດີກວ່ານີ້ແມ່ນການ ນຳ ໃຊ້ຂໍ້ເທັດຈິງບາງຢ່າງທີ່ພວກເຮົາຮູ້. ພວກເຮົາຮູ້ວ່າແຮ່ທາດສາມາດເຂົ້າມາຫາຫ້ອງປະຈຸບັນໄດ້ຈາກຈຸລັງສາມຈຸລັງ, ເຊິ່ງເປັນຈຸລັງທີ່ຢູ່ເບື້ອງຊ້າຍມືຂອງຈຸລັງປະຈຸບັນ, ແຕ່ລະຫ້ອງທີ່ຢູ່ ເໜືອ ຫ້ອງເບື້ອງຊ້າຍນີ້, ແລະຈຸລັງທີ່ຢູ່ເບື້ອງລຸ່ມຂອງຈຸລັງເບື້ອງຊ້າຍນີ້. ດັ່ງນັ້ນພວກເຮົາສາມາດເອົາສູງສຸດຂອງສາມຄ່ານີ້ຈະໃຫ້ພວກເຮົາມີຫຼຽນສູງສຸດເຊິ່ງສາມາດເກັບໄດ້ຖ້າພວກເຮົາຢູ່ໃນຫ້ອງປະຈຸບັນ. ສະນັ້ນ, ພວກເຮົາຈະ ນຳ ໃຊ້ ການຂຽນໂປແກຼມແບບເຄື່ອນໄຫວ ເພື່ອເກັບຮັກສາຜົນໄດ້ຮັບ ສຳ ລັບຈຸລັງປະຈຸບັນ. ນັ້ນແມ່ນ ຈຳ ນວນຫຼຽນສູງສຸດທີ່ສາມາດເກັບໄດ້ຖ້າຜູ້ແຮ່ທາດເຂົ້າມາໃນຫ້ອງປະຈຸບັນ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບບັນຫາ 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. ຄວາມສັບສົນທີ່ໃຊ້ເວລາແມ່ນ polynomial.

ຄວາມສັບສົນໃນອະວະກາດ

O (1), ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ ນຳ ໃຊ້ມາຕຣິກເບື້ອງເບື້ອງຕົ້ນເພື່ອເຮັດວຽກ. ພວກເຮົາບໍ່ໄດ້ ນຳ ໃຊ້ຕາຕະລາງ / ຕາຂ່າຍໄຟຟ້າເພີ່ມເພື່ອເກັບຜົນໄດ້ຮັບລະດັບກາງ. ແຕ່ໂປແກຼມລວມທັງ ໝົດ ຕ້ອງການຄວາມສັບສົນດ້ານອະວະກາດ O (N * M).