A# Question

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number I picked is higher or lower.

However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.

Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.

猜數(shù)字游戲，A在1-n中選擇一個(gè)數(shù)字，當(dāng)B猜中A選擇的數(shù)字，B就贏得比賽。每當(dāng)B猜錯(cuò)，A會(huì)告訴B是否太大還是太小，同時(shí)B要給A對(duì)應(yīng)猜的數(shù)字的錢。現(xiàn)在給出n，請(qǐng)你找出你保證贏得比賽所需花費(fèi)的最少的錢

Example

n = 10, I pick 8.

First round: You guess 5, I tell you that it’s higher. You pay $5. Second round: You guess 7, I tell you that it’s higher. You pay $7. Third round: You guess 9, I tell you that it’s lower. You pay $9.

Game over. 8 is the number I picked.

You end up paying 5 + 7 + 9 = 21.

這里的例子給出的21只是一種猜測(cè)情況所需的花費(fèi)，而不是題目的答案

Solution

根據(jù)上面的思路，我們定義dp[i][j]：在[i, j]范圍中保證贏得游戲所需花費(fèi)最少的錢。因?yàn)槭亲顗牡那闆r，所以在策略最優(yōu)的情況下，B始終不會(huì)猜中數(shù)字，那么當(dāng)B猜數(shù)字x的情況下，子問題將會(huì)出現(xiàn)兩種情況“猜的數(shù)字過小”，“猜的數(shù)字過大”，我們只需要比較出花費(fèi)較多的情況即可，所以B猜數(shù)字x的最大花費(fèi)為：B_Choose_X = x + max(dp[i][x - 1]， dp[x + 1][j])，在得到A選擇任意x，B所需的最大花費(fèi)時(shí)，dp[i][j] = min{B_Choose_1, B_Choose_2, …, B_Choose_N}