数字が高いか低いかを推測するII


難易度 ミディアム
よく聞かれる Amazon (アマゾン) Google マイクロソフト
配列 動的計画法

問題文

「GuessNumberHigher or Lower II」は、GuessGameと呼ばれるゲームをプレイすることを示しています。 ゲームは私が1からnまでの数を選ぶと言います。 私が選んでいない番号を推測するときはいつでも、あなたがより高いまたはより低い番号を選ぶと言うつもりです。

そして重要で興味深い部分は、間違った数、たとえばxを選択した場合、その金額のx単位を支払うことになるということです。 正しい数字、つまり私が選んだ数字を推測すると、ゲームに勝つはずです。

n = 10、6を選びます。

最初に選択してください:あなたは2を推測します、それはより大きいです、それより上に行きます。 あなたは2ドルを支払うでしょう。

4番目の選択:あなたは4を推測します、それはより大きいです、それより上に行きます。 あなたはXNUMXドルを支払うでしょう。

5番目の選択:あなたは5を推測します、それはより大きいです、それより上に行きます。 あなたはXNUMXドルを支払うでしょう。

正しい数字の6を選んだので、ゲームは終了しました。

最終的に$ 2 + $ 4 + $ 5 = $ 11を支払うことになります。

n≥1の数字が与えられた場合、この十分な金額でこのゲームに勝つことを保証できるように、必要な金額を決定するとします。

数字が高いか低いかを推測するII

数の多いまたは低い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) where 「n」 選択できる数値の範囲です。

スペースの複雑さ

O(n log n) where 「n」 選択できる数値の範囲です。