猜數更高或更低II


難度級別
經常問 亞馬遜 谷歌 Microsoft微軟
排列 動態編程

問題陳述

“ Guess Number Higher or Lower II”指出我們將玩一個名為Guess Game的遊戲。 遊戲說我選擇一個從1到n的數字。 每當您猜到我沒有選擇的數字時,我要說的是,您選擇一個更高或更低的數字。

重要且有趣的部分是,如果您選擇了錯誤的數字(例如x),那麼您將需要支付x單位的金額。 當您猜到正確的數字(即我所選擇的數字)時,您應該會贏得比賽。

n = 10,我選擇6。

首先選擇:您猜到2,它比那還大。 您將支付$ 2。

第二選擇:您猜4,它比那還大。 您將支付$ 4。

第三選擇:您猜5,它比那還大。 您將支付$ 5。

遊戲已經結束,因為您選擇了正確的數字6。

您最終需要支付$ 2 + $ 4 + $ 5 = $ 11。

假設,如果給定一個n≥1的數字,請確定您應該擁有多少錢,以便可以確保以這個足夠的金額贏得這場比賽。

猜數更高或更低II

Guess Number高低II問題的算法

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 這樣我們就可以找到足夠的錢來保證贏錢,為此,我們可以假設一個數字並在該數字以下和該數字之上執行操作。 這段代碼將 遞歸地 調用其功能。

這個問題希望你能 最小化最大值 您必須支付的金額才能贏。 當然,如果猜測不同,獲勝所需的費用也不同。但是我們的目標是計算出猜測1…n之間的數字所需的最小金額,

result = Math.min(result,amount(i))[返回所提供的輸入的最小值]

其中amount(i)是猜測數字i的最壞情況可能的數量。

現在,最糟糕的情況是當您假設3時。

您選擇了1,在最佳情況下1可能是您必須猜測的數字,因此,amount(i)= 0,但是我們對此並不感到煩惱,我們擔心的是最壞的情況,即1是不是所選擇的號碼。 因此,當選擇1時的成本為=(1)的成本+ 2,3成本。

您選擇了2,在最佳情況下2是答案,成本為0,但是在最壞情況下,答案是3或1是答案,並且在猜出一個數字後,您始終會知道選擇的數字是否更大或小於數字,因此我們將知道1是答案或3是答案。 因此,最壞情況下的成本是2。

選擇3,最壞情況的成本將是(3)中的1,2+成本。 最終成本將是所有這些最壞情況的成本中的最小值。 我們必須遞歸執行此操作以獲得答案,然後記住它。

履行

猜數字更高或更低II的C ++程序

#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

猜猜數字更高或更低II的Java程序

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” 是可以選擇的數字範圍。

空間複雜度

O(n log n) 哪裡 “ n” 是可以選擇的數字範圍。