375. Guess Number Higher or Lower II

发表于 | 分类于 | | 阅读次数:

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.

Example:

1
2
3
4
5
6
7
8
9
10
>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.
>

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

题意：和上一道不一样，的是每次猜了以后要付出相应的金额，所以要用到DP。

提示里说到这是一个Minimax问题，也就是最小的最大值问题。

分析：在1-n个数里面，我们任意猜一个数(设为i)，保证获胜所花的钱应该为 i + max(cost(1 ,i-1), cost(i+1 ,n))，这里cost(x,y))表示猜范围在(x,y)的数保证能赢应花的钱，则我们依次遍历 1-n作为猜的数，求出其中的最小值即为答案

我理解的，i为你在这个范围内猜的第一个数，这里的最小最大值问题中的最大值的意思就是考虑最坏的情况，所以猜i的最大值中答案肯定不是i，那么就要去找1-i-1和i+1-n这两个范围，而最小最大值的最小的意思是指取能使最后答案最小的i的值。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private int cost(int[][] acount, int start, int end){
	if(start>=end){
		return 0;
	}
	if(acount[start][end]!=0){
		return acount[start][end];
	}
	int re=Integer.MAX_VALUE;
	for(int i=start; i<=end; i++){
		int cost=i+Math.max(cost(acount, start, i-1), cost(acount, i+1, end));
		re=Math.min(re, cost);
	}
	acount[start][end]=re;
	return re;
}

public int getMoneyAmount(int n) {
	int[][] acount=new int[n+1][n+1];
	return cost(acount, 1, n);
}

参考地址：http://blog.csdn.net/adfsss/article/details/51951658