နံပါတ်အဆင့်မြင့်သို့မဟုတ်အောက် II ကိုခန့်မှန်းပါ


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

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

Guess Number Higher or Lower II ကကျွန်တော်တို့ဟာ Guess Game လို့ခေါ်တဲ့ဂိမ်းကိုကစားတော့မယ်လို့ဖော်ပြထားတယ်။ ဂိမ်းကကျွန်တော် ၁ မှ n အထိနံပါတ်ရွေးသည်။ ငါမရွေးသောဂဏန်းကိုသင်ခန့်မှန်းတိုင်း၊ သင်ကနံပါတ်ပိုမြင့်သို့မဟုတ်နိမ့်သည်ဟုသင်ပြောလိမ့်မည်။

အရေးကြီးဆုံးနှင့်စိတ်ဝင်စားစရာကောင်းတဲ့အချက်ကသင်မှားယွင်းသောနံပါတ်ကိုရွေးလျှင် x လို့ဆိုပါကသင်က x ၏ယူနစ်ကိုပေးချေတော့မည်ဖြစ်သည်။ နံပါတ်အမှန်ကိုခန့်မှန်းသောအခါသင်ဂိမ်းကိုအနိုင်ရလိမ့်မည်ဟုဆိုလိုသည်။ ဆိုလိုသည်မှာ၎င်းသည်ငါရွေးသောအရေအတွက်ဖြစ်သည်။

နမူနာ

n = 10, ငါ 6 ကောက်။

ပထမ ဦး ဆုံးရွေးပါ။ သင်ခန့်မှန်းနေသည် ၂ ထက်ကြီးသည်၊ အထက်ထက် ပို၍ သာသွားပါ။ သင် $ 2 ပေးပါလိမ့်မယ်

ဒုတိယရွေးပါ။ ၄ ခန့်မှန်းရမယ်၊ ပိုကြီးသည်၊ အထက်ထက်ပိုပါ။ မင်း $ 4 ပေးလိမ့်မယ်

တတိယရွေးပါ။ ၅ ခန့်မှန်းသည်ထက်ပိုနိုင်သည်၊ မင်း $ 5 ပေးလိမ့်မယ်

သငျသညျ 6 ကြောင်းမှန်ကန်သောနံပါတ်ကောက်သောကြောင့်ဂိမ်းယခုပြီးပြီ။

သင် $ 2 + $ 4 + $ 5 = $ 11 ပေးဆောင်ရသည်။

အကယ်၍ သင့်အား n ≥ 1 ဖြစ်သောနံပါတ်တစ်ခုပေးခဲ့ပါကသင်ဤဂိမ်းကိုအနိုင်ရမည့်ငွေပမာဏနှင့်သင်သေချာနိုင်စေရန်သင့်တွင်ငွေမည်မျှရှိသင့်သည်ကိုဆုံးဖြတ်ပါ။

နံပါတ်အဆင့်မြင့်သို့မဟုတ်အောက် II ကိုခန့်မှန်းပါ

Guess Number Higher or Lower II ပြproblemနာအတွက် Algorithm

1. Declare a 2-d array of size n+1.
2. Set output to the maximum value of an integer.
3. Set val to start + (end – start) / 2.
4. While val is less than or equal to end,
  1. Recursively call the function and find out the maximum between the values and Set table [start][end] to x + maximum of the number below the x value and number greater than the x value.
  2. Find out the minimum between the output and table[start][end] and update it into the output.
  3. Increase the value of x by 1.
4. Return table [start][end].

ရှင်းလင်းချက်

ကျနော်တို့ကနံပါတ်ပေးပြီ n ငါတို့ရဲ့အနိုင်ရမှုကိုအာမခံနိုင်မယ့်ငွေအလုံအလောက်ကိုရှာတွေ့နိုင်အောင်ဒီကိန်းဂဏန်းကိုယူပြီးအဲဒီနံပါတ်ရဲ့အောက်နဲ့အထက်နံပါတ်တွေပေါ်မှာလည်ပတ်နိုင်ပါတယ်။ ဒီကုဒ်ကသွားမယ် ပြန်လည် ၎င်း၏လုပ်ဆောင်ချက်များကိုခေါ်ပါ။

အဆိုပါပြproblemနာကိုသင်မျှော်လင့်ထား အများဆုံး minimize လုပ်ပါ အနိုင်ရနိုင်ရန်သင်ပေးရမည့်ငွေပမာဏ အကယ်၍ ကွဲပြားသောခန့်မှန်းချက်တစ်ခုအနိုင်ရရန်မတူညီသောကုန်ကျစရိတ်ရှိသည်မှာသေချာသည်။ သို့သော်ကျွန်ုပ်တို့၏ရည်မှန်းချက်မှာနံပါတ် ၁ ကိုအကြားခန့်မှန်းရန်အတွက်အနည်းဆုံးပမာဏကိုတွက်ချက်ရန်ဖြစ်သည်။

result = Math.min (ရလဒ်၊ ငွေပမာဏ (i)) [ပေးထားတဲ့သွင်းအားစုအနည်းဆုံးကိုပြန်ပို့သည်]

ဘယ်မှာပမာဏ (i) သည်နံပါတ်ခန့်မှန်းဘို့အဆိုးဆုံးဖြစ်နိုင်သောငွေပမာဏဘယ်မှာ။

အခု 3 ကိုသင်ယူဆတဲ့အခါအဆိုးဆုံးကဘာလဲ။

သင်ရွေးလိုက်သည်။ အကောင်းဆုံးကိစ္စ - ၁ တွင်သင်ခန့်မှန်းရမည့်နံပါတ်ဖြစ်မည်။ ထို့ကြောင့်ပမာဏ (i) = 1 သို့ဖြစ်သော်လည်းကျွန်ုပ်တို့စိတ်အနှောင့်အယှက်မဖြစ်ပါ။ ကျွန်ုပ်တို့သည်အဆိုးဆုံးကိစ္စနှင့်သက်ဆိုင်သည်။ မရွေးအရေအတွက်။ ထို့ကြောင့် 1 ကောက်ယူသောအခါကုန်ကျစရိတ်သည် (0) မှ 1+ ကုန်ကျမှုဖြစ်သည်။

မင်းက ၂ ကိုရွေးလိုက်တယ်၊ အကောင်းဆုံးကိစ္စက ၂ ကအဖြေဖြစ်ပြီး၊ ကုန်ကျစရိတ်က ၀ ဖြစ်တယ်။ ဒါပေမဲ့အဆိုးဆုံးမှာ ၃ ဒါမှမဟုတ် ၁ ကအဖြေဖြစ်တယ်။ နံပါတ်ကိုခန့်မှန်းတဲ့အခါရွေးလိုက်တဲ့နံပါတ်ကကြီးလားဆိုတာအမြဲတမ်းသိလာလိမ့်မယ်။ ဒါမှမဟုတ်ဒီထက်နည်းတဲ့ကိန်းကိုသိချင်ရင် ၁ ကအဖြေလား၊ ၃ ကအဖြေဖြစ်တယ်။ ဤအရပ်မှအဆိုးဆုံးကုန်ကျစရိတ် 2 ဖြစ်ပါတယ်။

အဆိုးဆုံးကုန်ကျစရိတ် (၃) ခုသည်ကုန်ကျစရိတ် (၁၊၂) မှ ၃+ အထိကျလိမ့်မည်။ နောက်ဆုံးကုန်ကျစရိတ်သည်ဤအဆိုးဆုံးကုန်ကျစရိတ်အားလုံး၏အနည်းဆုံးဖြစ်သည်။ အဖြေရရန်အပြန်အလှန်အားဖြင့်ကျွန်ုပ်တို့ဤအရာကိုပြန်လည်တုံ့ပြန်ရမည်။

အကောင်အထည်ဖော်ရေး

Guess Number Higher or Lower II ပြforနာအတွက် C ++ program

#include<iostream>
#include<vector>

using namespace std;

int helper(int low,int high,vector<vector<int>> &dp)
{
    if(low>=high)
        return 0;
    if(dp[low][high]!=INT_MAX)
        return dp[low][high];
    for(int j=low; j<=high; j++)
    {
        dp[low][high]=min(dp[low][high],max(j+helper(low,j-1,dp),j+helper(j+1,high,dp)));
    }
    return dp[low][high];

}
int getMoneyAmount(int n)
{
    vector<vector<int>> dp(n+1,vector<int>(n+1,INT_MAX));
    return helper(1,n,dp);
}

int main()
{
    cout<<getMoneyAmount(10);
}
16

Guess Number Higher or Lower II ပြforနာအတွက် Java program

class guessNumber
{
    public static int getNumber(int n)
    {
        return guessNumberRec(new int[n+1][n+1], 1, n);
    }
    public static int guessNumberRec(int[][] arr, int left, int right)
    {
        if (left >= right)
        	return 0;
        if (arr[left][right] != 0)
        	return arr[left][right];

        arr[left][right] = Integer.MAX_VALUE;
        for (int a = left; a <= right; a++)
        {
            arr[left][right] = Math.min(arr[left][right], a + Math.max(guessNumberRec(arr, left, a - 1), guessNumberRec(arr, a + 1, right)));
        }
        return arr[left][right];
    }
    public static void main(String [] args)
    {
        System.out.println(getNumber(10));
    }
}
16

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

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

အို (။2) ဘယ်မှာ “ n” ရွေးချယ်နိုင်သောနံပါတ်များ၏အကွာအဝေးဖြစ်ပါတယ်။

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

အို (n log n) ဘယ်မှာ “ n” ရွေးချယ်နိုင်သောနံပါတ်များ၏အကွာအဝေးဖြစ်ပါတယ်။