[LeetCode]Guess Number Higher or Lower II

题目的描述很不清楚，我们需要弄清楚它的意思。它的意思是，对于1-n的数，主持人选择任意的数k，求我们需要的最少的钱来赢的这个游戏。例如：1，2，3，我们有以下情况：

• 如果我们先取1，最坏的情况cost = 3
• 假设k = 1，cost = 0
• 假设k = 3，我们取1之后只需要最多花两块钱就可以赢，因为我们直接取2，如果不是答案我们立马就可以知道答案是3。假设我们取3的话我们需要花费更多的钱，cost = 3
• 同理k = 2，cost = 1，因为我们之后一定取2，应为cost更少
• 如果我们先取2，最坏情况cost = 3
• 假设k = 2, cost = 0
• 假设k = 1， cost = 2
• 假设k = 3，cost = 2 + 1 = 3
• 如果先取3，最坏情况cost = 4
• 假设k = 3， cost = 0
• 假设k = 1，cost = 3
• 假设k = 2，cost = 3 + 1 = 4

所以最小的cost的情况对于我们先取1或者2的情况，我们需要3块钱来保证赢。我们假设用cost[i][j]来表示对于[i, j]范围我们保证可以赢的最小资金。递推公式为：

• cost[i][j] = min(k + max(cost[i][k - 1], cost[k + 1][j])), where i <= k <= j

max对应的是主持人选择的数在左半边或者右半边的更坏的情况，也就是使cost更贵的情况，如果选择的数就是k的话其cost显然更小，我们这里就不需要考虑了。我们要取更坏的情况。min对应的是这次pick我们取的数能使总的cost[i][j]更小的情况，显然对于[i,j]的数，我们应该选择能使cost[i][j]最小的数来进行游戏。假设输入1-n的数，时间复杂度O(n^3)，空间复杂度O(n^2)，代码如下：

	class Solution {
	public:
	int getMoneyAmount(int n) {
	vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
	for(int k = 2; k <= n; ++k)
	{
	for(int i = 1; i <= n - k + 1; ++i)
	{
	int cost = INT_MAX;
	for(int j = i; j < i + k; ++j)
	{
	cost = min(cost, j + max(j - 1 >= i? dp[i][j - 1]: 0, i + k - 1 >= j + 1? dp[j + 1][i + k - 1]: 0));
	}
	dp[i][i + k - 1] = cost;
	}
	}
	return dp[1][n];
	}
	};

view raw Guess Number Higher or Lower II.cpp hosted with ❤ by GitHub