ရွှေတွင်းပြProbleနာ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Flipkart Google Microsoft က PayU Uber
အခင်းအကျင်း Dynamic Programming matrix

ပြProbleနာဖော်ပြချက်

“ Gold Mine ပြproblemနာ” ကသင့်အား 2D ပေးထားသည်ဟုဖော်ပြသည် ဇယားကွက် ပေးထားသောဇယားကွက်တစ်ခု၏ဆဲလ်တစ်ခုစီတွင်အနုတ်လက္ခဏာမဟုတ်သောဒင်္ဂါးပြားအချို့ရှိနေခြင်း။ အစပိုင်းတွင်သတ္တုတွင်းသည်ပထမကော်လံတွင်ရပ်နေသော်လည်းအတန်းတွင်ကန့်သတ်ချက်များမရှိပါ။ သူသည်မည်သည့်အတန်းတွင်မဆိုစတင်နိုင်သည်။ မိုင်းလုပ်သားသည်လမ်းကြောင်းနောက်သို့သာနောက်ကော်လံသို့သာရွေ့နိုင်သည်။ သူလည်းထောင့်ဖြတ်အတွက်ရွှေ့နိုင်ပါတယ်။ ဒီတော့ဆဲလ်တစ်ခုစီမှသင့်ဆီမှာညာဘက်၊ ညာဘက်၊ ညာဘက်အောက်ထောင့်သုံးခုရှိတယ်။ သို့သော်ဆဲလ်သည်ဇယားကွက်၏နယ်နိမိတ်အတွင်းရှိသင့်သည်။ သငျသညျသူစုဆောင်းနိုငျသောရွှေဒင်္ဂါးအရေအတွက်အများဆုံးကဘာလဲဆိုတာရှာတွေ့ဖို့လိုအပ်?

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

ရှင်းလင်းချက် - လမ်းကြောင်းအတွက်ပုံကိုကြည့်ပါ။ ရွှေဒင်္ဂါး ၁၅၀ စုဆောင်းရန်မိုင်းလုပ်သားရွေးချယ်သင့်သည်။

ရွှေတွင်းပြProbleနာ

ရွှေတွင်းပြProbleနာအတွက်ချဉ်းကပ်နည်း

နော့ဗ်ချဉ်းကပ်နည်းသည်သတ္တုတွင်းတူးသူမှပထမကော်လံမှနောက်ဆုံးကော်လံသို့သွားသောလမ်းကြောင်းများအားလုံးကိုထုတ်လုပ်ရန်နောက်ပြန်လမ်းကြောင်းကိုအသုံးပြုခြင်းဖြစ်သည်။ လမ်းကြောင်းတစ်ခုစီတိုင်းအတွက်စုဆောင်းထားသောရွှေဒင်္ဂါးအရေအတွက်ကိုတွက်ချက်ပါ။ သို့သော်ဤချဉ်းကပ်မှုသည်အချိန်ကုန်ပြီးကျွန်ုပ်တို့ဇယားကွက်၏အရွယ်အစားကိုတိုးမြှင့်သည်နှင့်အမျှအချိန်ကာလကျော်လွန်သွားလိမ့်မည်။

ပိုမိုကောင်းမွန်သောချဉ်းကပ်နည်းသည်ကျွန်ုပ်တို့သိထားသည့်အချက်အလက်အချို့ကိုအသုံးပြုခြင်းဖြစ်သည်။ ငါတို့သိသည်မှာမိုင်းလုပ်သားသည်လက်ရှိဆဲလ်သို့သုံးဆဲလ်မှလာနိုင်သည်၊ လက်ရှိဆဲလ်၏ဘယ်ဘက်သို့ရောက်သောဆဲလ်၊ ဤလက်ဝဲဘက်ဆဲလ်အထက်ရှိဆဲလ်နှင့်ဘယ်ဖက်ဆဲလ်အောက်ခြေရှိဆဲလ်များမှသာလာနိုင်သည်။ ဒီတော့ဒီတန်ဖိုးသုံးခုကိုအမြင့်ဆုံးယူနိုင်တယ်၊ ငါတို့ကလက်ရှိဆဲလ်မှာရှိနေရင်စုဆောင်းနိုင်တဲ့အများဆုံးဒင်္ဂါးတွေကိုပေးလိမ့်မယ်။ ဒါကြောင့်ငါတို့သုံးပါလိမ့်မယ် dynamic programming ကို မည်သည့်လက်ရှိဆဲလ်များအတွက်ရလဒ်သိုလှောင်ရန်။ ဆိုလိုသည်မှာလက်ရှိဆဲလ်သို့မိုင်းတွင်းသို့ရောက်ရှိပါကအကြွေစေ့အမြောက်အများစုဆောင်းနိုင်သည်။

ကုဒ်

Gold Mine ပြforနာအတွက် C ++ code

#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

Gold Mine ပြforနာအတွက် Java code

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N * M)အကြောင်းကတော့ကျွန်တော်တို့ဇယားကွက်အားလုံးကိုဖြတ်သွားရလို့ပဲ။ ပြီးတော့အဲဒါမှာ N * M ဆဲလ်တွေရှိတယ်။ အချိန်ရှုပ်ထွေး polynomial ဖြစ်ပါတယ်။

အာကာသရှုပ်ထွေးမှု

အို (၁)ကျနော်တို့အပေါ်သို့လုပ်ကိုင်ဖို့ကန ဦး matrix ကိုအသုံးပြုသောကတည်းက။ အလယ်အလတ်ရလဒ်များကိုသိုလှောင်ရန်အတွက်မည်သည့်အပို matrix / grid ကိုကျွန်ုပ်တို့မသုံးခဲ့ပါ။ သို့သော်အစီအစဉ်တစ်ခုလုံးအနေဖြင့်အို (N * M) အာကာသရှုပ်ထွေးမှုကိုလိုအပ်သည်။