375. Guess Number Higher or Lower II

今天的题目是375. Guess Number Higher or Lower II。

一道动态规划问题，一开始以为是通过二分查找的方式来计算就好了，但是后面发现这样算出来答案不是最优的。

思路大概是这样的，把问题先泛化为，给定从i到j的数字，猜数字的最大代价，为了得到最大代价，我们不妨假设每次都猜错，直到只有一个元素时。

第一次猜的时候，我们可以猜从i到j的任意一个数字k，这时代价为k，猜错后可能得到两种回答，比k大或者比k小，这时我们的问题转换为两个子问题：

• 给定i到k-1的数字，猜数字的最大代价
• 给定k+1到j的数字，猜数字的最大代价

当i到j的数字的数目小于等于1时，代价为0。

据此，我们可以写出以下动态规划方程：

$$
dp[i,j] = \left{
\begin{aligned}
0 & , & (j - i + 1) >= 0 \
min_{i<=k<=j}{dp[i,k-1] + k + dp[k+1,j]} & , & others
\end{aligned}
\right.
$$

由于计算dp[i,j]需要dp[i,k-1]和dp[k+1,j]，所以我们可以直到它是沿着斜对角线计算得到dp[1,n]的,如下图所示:

因此，我们可以根据动态规划方程写出如下代码：

int getMoneyAmount(int n) {
	vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
	for (int step = 1;step < n;step++) {
		for(int i = 1,j = 1 + step;j <= n;i++,j++) {
			// int j = i + step;
			// if (j > n) break;
			// dp[i][j] = INT_MAX;
			dp[i][j] = dp[i][j-1] + j;
			for(int k = i;k < j;k++) {
				dp[i][j] = min(dp[i][j], k + max(dp[i][k-1], dp[k+1][j]));
			}
		}
	}
	return dp[1][n];
}