# 猜數更高或更低II

## 問題陳述

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

n = 10，我選擇6。

## 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].```

## 解釋

result = Math.min（result，amount（i））[返回所提供的輸入的最小值]

## 履行

### 猜數字更高或更低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” 是可以選擇的數字範圍。