mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
49 lines
2.1 KiB
Markdown
49 lines
2.1 KiB
Markdown
# [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];
|
||
}
|
||
};
|
||
```
|
||
|