Guess Number Higher or Lower II

Guess Number Higher or Lower II

这个题目还是蛮有意思的 给定整数n,假定我选中的数1到n中的C,我只提示你猜的数与C的大小关系,这样你就可以缩小范围,继续猜测,但是你猜错数字,就要支付等值的美元,我为了获得更多的美元,会通过高低引导你,比如 n = 10 1,2,3,4,5,6,7,8,9,10 这时候如果你第一次选中9,我要是提示你猜小了,则你下一个就可以猜出10,因为只有一个数可以选择,那么我只能得到9美元,如果我告诉你猜高了,还有很多数字可选,这样我也可以获得更多美元。

假如你第一次选择的是7,如果告诉你猜低了,往高了猜你会猜几呢,一开始觉得猜7+10均值8,那么我可以告诉你还是猜低了,这时候你再猜8+10均值9,我还是可以告诉你猜低了,因为还有10,你要支付7+8+9,如果一个开始猜完7,直接猜测8+10均值9,这样无论我说猜低猜高了,你都可以获得答案是8或者10,只需支付7+9,16美元 这个题目可以用动态规划求解,不断就将问题分解成规模小子问题,终结条件就是问题不可分了。而且开始选择都是从中间往后开始猜,这样才能少支付美元,程序性能会提升很多

import numpy as np
class Solution(object):
    def getMoneyAmount(self, n):
        return self.dp(1, n)
        """
        :type n: int
        :rtype: int
        """
    dic = {}
    def dp(self, start, end):
        if (start, end) in self.dic:
            return self.dic[(start,end)]
        if start >= end:
            self.dic[(start,end)] = 0
            return 0
        elif (start == end - 1):
            self.dic[(start,end)] = start
            return start
        elif (start == end -2):
            self.dic[(start,end)] = start+1
            return start+1
        else:
            temp = np.maximum
            for i in range((start+end)/2, end+1,1):
                temp = min(temp, i + max(self.dp(start, i-1), self.dp(i+1, end)))
        self.dic[(start,end)] = temp
        return temp     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

VB.NET中图像处理的一些技巧以及其和C#图像处理的差距。

 早期的时候我使用的开发工具是VB6,VB6做图像处理的速度在我的软件Imageshop中有所体现,还是算可以的。目前,我已经改用C#来研究图像算法,C#中有...

21150
来自专栏数据分析

[数据清洗]-Pandas 清洗“脏”数据(一)

概要 准备工作 检查数据 处理缺失数据 添加默认值 删除不完整的行 删除不完整的列 规范化数据类型 必要的转换 ...

1K70
来自专栏向治洪

策略模式

策略(Strategy)模式 策略模式属于对象的行为模式。其用意是针对一组算法,将每一个算法封装到具有共同接口的独立的类中,从而使得它们可以相互替换。策略模式使...

20090
来自专栏大数据挖掘DT机器学习

用python对汽车油耗进行数据分析

- 从http://fueleconomy.gov/geg/epadata/vehicles.csv.zip 下载汽车油耗数据集并解压 - 进入jupyt...

40460
来自专栏吉浦迅科技

DAY59:阅读 #pragma unroll

By default, the compiler unrolls small loops with a known trip count. The #pragm...

6920
来自专栏PPV课数据科学社区

用python对汽车油耗进行数据分析

- 从http://fueleconomy.gov/geg/epadata/vehicles.csv.zip 下载汽车油耗数据集并解压 - 进入jupyte...

48680
来自专栏龙行天下CSIEM

科学瞎想系列之八十四 永磁电机(6)

【图片部分来自网络如有侵权敬请邮箱联系。欢迎原文转发到朋友圈,未经许可的媒体平台谢绝转载,如需转载或合作请邮件联系。联系邮箱laolicsiem@126.com...

32920
来自专栏吉浦迅科技

DAY79:阅读 Compute Capabilities

The general specifications and features of a compute device depend on its comput...

21120
来自专栏数据小魔方

你绝对想不到,数据地图还能这么玩~

这个周末刷微信的时候,偶然看到一篇关于R语言12月更新包的介绍,翻到底部看了一眼,刚好看到一个关于ggplot2的一个图层插件——geom_scatterpie...

35760
来自专栏数据小魔方

关于美国地图中的两个海外州坐标平移与原始投影问题~

通常我们在政治新闻或者财经日报中看到的数据可视化图表中,美国地图中的两个海外州——阿拉斯加和夏威夷都是被平移过的,主要因为这两个海外州偏离本土太远,使用原始位置...

31650

扫码关注云+社区

领取腾讯云代金券