今天的题目是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]的,如下图所示:

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

1
int getMoneyAmount(int n) {
2
  vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
3
  for (int step = 1;step < n;step++) {
4
    for(int i = 1,j = 1 + step;j <= n;i++,j++) {
5
      // int j = i + step;
6
      // if (j > n) break;
7
      // dp[i][j] = INT_MAX;
8
      dp[i][j] = dp[i][j-1] + j;
9
      for(int k = i;k < j;k++) {
10
        dp[i][j] = min(dp[i][j], k + max(dp[i][k-1], dp[k+1][j]));
11
      }
12
    }
13
  }
14
  return dp[1][n];
15
}