375. 猜数字大小 II

喜欢ヅ旅行 2022-10-10 04:43 188阅读 0赞

> 我们正在玩一个猜数游戏，游戏规则如下：
> 
> 我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。
> 
> 每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
> 
> 然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
> 
> 示例:
> 
> n = 10, 我选择了8.
> 
> 第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。  
> 第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。  
> 第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
> 
> 游戏结束。8 就是我选的数字。
> 
> 你最终要支付 5 + 7 + 9 = 21 块钱。

class Solution {
        Long [][] memo;
        /**
        记忆化递归
         */
        public int getMoneyAmount(int n) {
            memo=new Long[n+1][n+1];
            return (int)helper(1,n);
    
        }
        public long helper(int low,int high){
            if(low>=high){//猜对了 或者越界
                return 0;
            }
            if(memo[low][high]!=null){
                return memo[low][high];
            }
            long min=Integer.MAX_VALUE;
            long res=0;
            for(int i=low;i<=high;i++){
                res=( i+Math.max(helper(low,i-1),helper(i+1,high)) );//一定要最大值,满足两者才可以          
                min=Math.min(min,res);
            }
             memo[low][high]=min;
            return min;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，188人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode：猜数字大小

们正在玩一个猜数字游戏。游戏规则如下：我从 1 到 n 选择一个数字。你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调...

小鱼儿/ 2024年04月17日 05:44/ 0 赞/ 94 阅读

相关猜数字大小 II

力扣链接 [力扣][Link 1] 题目描述：我们正在玩一个猜数游戏，游戏规则如下： 1. 我从 `1`到 `n` 之间选择一个数字。 2. 你来猜我选了哪个数字

迈不过友情╰/ 2024年03月26日 11:39/ 0 赞/ 30 阅读

相关 leetcode374. 猜数字大小

我们正在玩一个猜数字游戏。游戏规则如下：我从 1 到 n 选择一个数字。你需要猜我选择了哪个数字。每次你猜错了，我会告诉你这个数字是大了还是小了。你调用一

骑猪看日落/ 2023年07月03日 08:20/ 0 赞/ 27 阅读

相关 LeetCode题解：猜数字大小

猜数字大小（easy） > 更好的阅读体验应该是： > > 1. 审题-思考 > 2. 答题 > 3. 整理-归纳一、题目 [LeetCode：374.

红太狼/ 2022年12月27日 09:17/ 0 赞/ 348 阅读

相关 375. 猜数字大小 II

> 我们正在玩一个猜数游戏，游戏规则如下： > > 我从 1 到 n 之间选择一个数字，你来猜我选了哪个数字。 > > 每次你猜错了，我都会告诉你，我选的数字比你的大了或者

喜欢ヅ旅行/ 2022年10月10日 04:43/ 0 赞/ 189 阅读

相关 374. 猜数字大小

> 猜数字游戏的规则如下： > > 每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。 > 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字

港控/mmm°/ 2022年10月08日 05:48/ 0 赞/ 190 阅读

相关 374. 猜数字大小

猜数字游戏的规则如下：每轮游戏，我都会从 1 到 n 随机选择一个数字。请你猜选出的是哪个数字。如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

待我称王封你为后i/ 2022年10月06日 14:56/ 0 赞/ 216 阅读

相关 374. 猜数字大小

2021-06-14 LeetCode每日一题链接：[https://leetcode-cn.com/problems/guess-number-higher-or-l

秒速五厘米/ 2022年10月06日 14:53/ 0 赞/ 217 阅读

相关 leetcode 375. Guess Number Higher or Lower II | 375. 猜数字大小 II（动态规划思路总结）

题目 [https://leetcode.com/problems/guess-number-higher-or-lower-ii/][https_leetcode.co

超、凢脫俗/ 2022年08月31日 01:58/ 0 赞/ 124 阅读

相关猜数字大小游戏

用while语句写猜大小游戏普通版 n =80 user\_input = int(input("请输入一个数:") while True: 　　if user\_

素颜马尾好姑娘i/ 2021年12月14日 15:59/ 0 赞/ 377 阅读