网站开发与设计结课论文,廊坊网站制作建设,网站关键词seo费用,北京外包公司排行榜375. 猜数字大小 II
我们正在玩一个猜数游戏#xff0c;游戏规则如下#xff1a;
我从 1 到 n 之间选择一个数字。你来猜我选了哪个数字。如果你猜到正确的数字#xff0c;就会 赢得游戏 。如果你猜错了#xff0c;那么我会告诉你#xff0c;我选的数字比你的 更大或者更…375. 猜数字大小 II
我们正在玩一个猜数游戏游戏规则如下
我从 1 到 n 之间选择一个数字。你来猜我选了哪个数字。如果你猜到正确的数字就会 赢得游戏 。如果你猜错了那么我会告诉你我选的数字比你的 更大或者更小 并且你需要继续猜数。每当你猜了数字 x 并且猜错了的时候你需要支付金额为 x 的现金。如果你花光了钱就会 输掉游戏 。 给你一个特定的数字 n 返回能够 确保你获胜 的最小现金数不管我选择那个数字 。 示例 1输入n 10
输出16
解释制胜策略如下
- 数字范围是 [1,10] 。你先猜测数字为 7 。- 如果这是我选中的数字你的总费用为 $0 。否则你需要支付 $7 。- 如果我的数字更大则下一步需要猜测的数字范围是 [8,10] 。你可以猜测数字为 9 。- 如果这是我选中的数字你的总费用为 $7 。否则你需要支付 $9 。- 如果我的数字更大那么这个数字一定是 10 。你猜测数字为 10 并赢得游戏总费用为 $7 $9 $16 。- 如果我的数字更小那么这个数字一定是 8 。你猜测数字为 8 并赢得游戏总费用为 $7 $9 $16 。- 如果我的数字更小则下一步需要猜测的数字范围是 [1,6] 。你可以猜测数字为 3 。- 如果这是我选中的数字你的总费用为 $7 。否则你需要支付 $3 。- 如果我的数字更大则下一步需要猜测的数字范围是 [4,6] 。你可以猜测数字为 5 。- 如果这是我选中的数字你的总费用为 $7 $3 $10 。否则你需要支付 $5 。- 如果我的数字更大那么这个数字一定是 6 。你猜测数字为 6 并赢得游戏总费用为 $7 $3 $5 $15 。- 如果我的数字更小那么这个数字一定是 4 。你猜测数字为 4 并赢得游戏总费用为 $7 $3 $5 $15 。- 如果我的数字更小则下一步需要猜测的数字范围是 [1,2] 。你可以猜测数字为 1 。- 如果这是我选中的数字你的总费用为 $7 $3 $10 。否则你需要支付 $1 。- 如果我的数字更大那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏总费用为 $7 $3 $1 $11 。
在最糟糕的情况下你需要支付 $16 。因此你只需要 $16 就可以确保自己赢得游戏。示例 2输入n 1
输出0
解释只有一个可能的数字所以你可以直接猜 1 并赢得游戏无需支付任何费用。示例 3输入n 2
输出1
解释有两个可能的数字 1 和 2 。
- 你可以先猜 1 。- 如果这是我选中的数字你的总费用为 $0 。否则你需要支付 $1 。- 如果我的数字更大那么这个数字一定是 2 。你猜测数字为 2 并赢得游戏总费用为 $1 。
最糟糕的情况下你需要支付 $1 。
解题思路
数组定义dp[i][j]代表从区间[i,j]里面猜数字能够 确保获胜 的最小现金数。初始化当ij时只能猜一个数字所以必定胜利不需要花费任何现金当ij时不存在实际意义状态转移从区间[i,j]里面猜数字遍历所有可能的选择在选择完猜测的数字k以后选择花费更大的区间进行下一轮的猜数字max(dp[i][k-1],dp[k1][j])因为我们必须确保能够获胜所以考虑的都是最坏的情况
代码
class Solution {
public:int getMoneyAmount(int n) {vectorvectorint dp(n1,vectorint(n1));for (int i n-1; i 1; i--) {for (int j i1; j n ; j) {int mINT_MAX;for (int k i; k j ; k) {mmin(m,kmax(dp[i][k-1],dp[k1][j]));}dp[i][j]m;}}return dp[1][n];}
};
