LC 375. Guess Number Higher or Lower II
2024-08-27 12:22:12
We are playing the Guess Game. The game is as follows:
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number I picked is higher or lower.
However, when you guess a particular number x, and you guess wrong, you pay $x. You win the game when you guess the number I picked.
Example:
n = 10, I pick 8. First round: You guess 5, I tell you that it's higher. You pay $5.
Second round: You guess 7, I tell you that it's higher. You pay $7.
Third round: You guess 9, I tell you that it's lower. You pay $9. Game over. 8 is the number I picked. You end up paying $5 + $7 + $9 = $21.
Given a particular n ≥ 1, find out how much money you need to have to guarantee a win.
Runtime: 56 ms, faster than 38.71% of C++ online submissions for Guess Number Higher or Lower II.
Memory Usage: 5.4 MB, less than 0.56% of C++ online submissions for Guess Number Higher or Lower II.
class Solution {
vector<vector<int>>dp;
public:
int getMoneyAmount(int n) {
dp.resize(n+, vector<int>(n+,));
return DP(,n);
} int DP(int s, int e) {
if(s >= e) return ;
if(dp[s][e] != ) return dp[s][e];
int res = INT32_MAX;
for(int x=s; x<=e; x++) {
int tmp = x + max(DP(s,x-),DP(x+,e));
res = min(res, tmp);
}
dp[s][e] = res;
return res;
}
};
最新文章
- Windows服务定时执行方式
- 数据结构和算法 &ndash; 4.字符串、 String 类和 StringBuilder 类
- python案例-用户登录
- C++中栈区 堆区 常量区
- 【数论,找规律】Uva 11526 - H(n)
- postgres 利用unique index代替 primay key
- jquery 点点滴滴小记
- 初识 python
- Basic Data Structure
- 树莓派用U盘安装系统
- 实时滚动图表绘制方法: LightningChart教程 + 源码下载
- K短路 (A*算法) [Usaco2008 Mar]牛跑步&;[Sdoi2010]魔法猪学院
- 【转】Unity四元数和向量相乘作用及其运算规则
- JMagic 操作 ImageMagick 处理图片
- haproxy(8):haproxy代理MySQL要考虑的问题
- python中raise的用法
- Hibernate 再接触 性能优化
- nginx的location、root、alias指令用法和区别
- [原创]delphi一次性批量在TScrollBox中显示N个复选框TCheckBox的源码
- 【原创】Your Connection is not private
热门文章
- C++——虚函数表解析
- Python 包文件安装
- 每日一题-——最长公共子序列(LCS)与最长公共子串
- K8S 1.12大特性最快最深度解析:Kubernetes CSI Snapshot(上)
- charles 过滤指定域名
- 第五次个人作业---Alpha2项目测试
- 使用Arduino开发板控制步进电机
- Linux网络编程综合运用之MiniFtp实现(九)
- vue 安装 ‘node-sass’ 运行报错:ERROR in Cannot find module &#39;node-sass&#39;
- effective Java 第三版学习笔记