LeetCode/solutions/375. Guess Number Higher or Lower II.md

# [375. Guess Number Higher or Lower II](https://leetcode.com/problems/guess-number-higher-or-lower-ii/)

# 思路

猜数游戏，若猜的x且猜错了则需要付出x元钱，问需要多少钱能保证猜对。即最坏情况下，至少需要花多少钱才能猜对。
根据提示我们发现可以根据动态规划来做，而且是个区间dp，我们设
```
dp[i][j]为在[i, j]内做猜数游戏的话计算出的结果, 最后返回dp[1][n]
```
来考虑一下初始值，设想一下我们在[4,5]之间（那就只有4和5两个数了）做猜数游戏，最坏情况下至少需要花多少钱呢，很明显是4块钱，所以
```
初始值: dp[i][i+1] = i, dp[i][i] = 0
```
那么转移方程呢？先考虑一下如果在[i, j]内做猜数游戏，那么为了最后尽可能少花钱，那么我们第一次应该猜哪个数（设为k）呢？
我们可以穷举k属于[i+1, j-1]来看k取何值时会让最终总花费最少，即计算dp[i][j]的转移方程为
```
for all k in [i+1, j-1]:
  dp[i][j] = min(dp[i][j], k + max(dp[i][k-1], dp[k+1][j]));
```

由上面转移方程看出，**我们应该反向枚举i而正向枚举j**。

时间复杂度O(n^3), 空间复杂度O(n^2)。

本题时间复杂度可优化至O(n^2)，可参考[1](https://artofproblemsolving.com/community/c296841h1273742)和[2](https://blog.csdn.net/Site1997/article/details/100168676)。
亲测确实快一些，但是乍一看没怎么看懂，留个坑吧。

> 注意：此题很容易错误地认为二分就是最优，但其实不是。二分只能保证猜测次数最小，而不是最坏情况下花费的钱最少。例如n=5，若采用二分，那么最坏情况下花费是3+4=7；但是实际上应该是4+2=6。

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