375. Guess Number Higher or Lower II.md

375. 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和2。 亲测确实快一些，但是乍一看没怎么看懂，留个坑吧。

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

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];
    }
};