做网站做哪个行业好,前端程序员,做直播网站找哪家网站好,合肥电脑网站建站题目大意#xff1a;
https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii
我们正在玩一个猜数游戏#xff0c;游戏规则如下#xff1a;
我从 1 到 n 之间选择一个数字。 你来猜我选了哪个数字。 如果你猜到正确的数字#xff0c;就会 赢得游戏 。 如果你…题目大意
https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii
我们正在玩一个猜数游戏游戏规则如下
我从 1 到 n 之间选择一个数字。 你来猜我选了哪个数字。 如果你猜到正确的数字就会 赢得游戏 。 如果你猜错了那么我会告诉你我选的数字比你的 更大或者更小 并且你需要继续猜数。 每当你猜了数字 x 并且猜错了的时候你需要支付金额为 x 的现金。如果你花光了钱就会 输掉游戏 。 给你一个特定的数字 n 返回能够 确保你获胜 的最小现金数不管我选择那个数字 。
样例1的例图 输入n 10
输出16
输入n 1
输出0
输入n 2
输出1
提示
1 n 200
解题报告
这个问题也可以看成是一个博弈问题但其实是让你做出一步决策然后考虑最差情况即可。换句话说做出的每一步决策是主动的然后面临的状况中要考虑最差的局面在做出下一次决策。看似可以二分但是无法证明这种决策方法的正确性最保险的方法就是枚举所有状态然后发现状态是可以dp的。dp[i][j]代表当前决策区间是[i,j]时的最小花费然后按照区间dp的方式更新dp数组就可以了。
内层k枚举每一个决策注意不要忘记了边界情况枚举i和j这两个端点。
AC代码
class Solution {
public:int max(int a, int b) {return ab?a:b;}int min(int a, int b) {return ab?a:b;}int getMoneyAmount(int n) {vectorvectorint dp(n1,vectorint(n1));for(int len 1; lenn; len) {for(int l 1; ln-len; l) {int r llen;dp[l][r] min(l dp[l1][r], r dp[l][r-1]);for(int k l1; kr-1; k) {dp[l][r] min(dp[l][r], max(dp[l][k-1], dp[k1][r]) k);}}}return dp[1][n];}
};
