logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
名人与名画。
avatar
名人与名画。# Joke - 肚皮舞运动
c*g
1 楼
我在看DP问题的时候，碰到了两个题目，很是疑惑
1 给你一个整数，不同的coin，然后求最少多少个coin可以得到这个整数。
我的疑问是，这个题目需要DP么？假设coin 是1，3， 5， 给定17，直接先除以5，
然后剩下的除以3，然后剩下的除以1，不就行了么？这样的算法得到的答案有错误么？
2 给你一个整数数组，有正有负，求连续的数的最大的和。
这个题目不是有一个n的算法么？需要DP么？
谢谢了
。
avatar
w*u
2 楼
经过长达两个statement的多次电话，邮件argue，貌似是解决了，之前的*4还没看到补
回来，两个月花了1008刀，现在TYP是2108，只是单独补了1000TYP，不知道卡的
program是不是真从下个statement开始改过来~不过citi客服水平真心令人捉急
最后感谢citi客服给了我如此多机会锻炼口语，精疲力竭
avatar
z*c
3 楼
avatar
r*t
4 楼
现实 coin set 贪心可解，对大部分假设的 coin set 贪心不能解，需要搜索回溯。

【在 c***g 的大作中提到】
: 我在看DP问题的时候，碰到了两个题目，很是疑惑
: 1 给你一个整数，不同的coin，然后求最少多少个coin可以得到这个整数。
: 我的疑问是，这个题目需要DP么？假设coin 是1，3， 5， 给定17，直接先除以5，
: 然后剩下的除以3，然后剩下的除以1，不就行了么？这样的算法得到的答案有错误么？
: 2 给你一个整数数组，有正有负，求连续的数的最大的和。
: 这个题目不是有一个n的算法么？需要DP么？
: 谢谢了
: 。
avatar
m*o
5 楼
forward的5x？客服怎么解释的？为什么之前不给你

★ 发自iPhone App: ChineseWeb 7.8

【在 w********u 的大作中提到】
: 经过长达两个statement的多次电话，邮件argue，貌似是解决了，之前的*4还没看到补
: 回来，两个月花了1008刀，现在TYP是2108，只是单独补了1000TYP，不知道卡的
: program是不是真从下个statement开始改过来~不过citi客服水平真心令人捉急
: 最后感谢citi客服给了我如此多机会锻炼口语，精疲力竭
avatar
C*n
6 楼
乔老爷呢？
avatar
r*n
7 楼
也不全对....对任何finite coin set...如果钱数足够大, 解一定是greedy的
但是这个门限要用DP来解

【在 r****t 的大作中提到】
: 现实 coin set 贪心可解，对大部分假设的 coin set 贪心不能解，需要搜索回溯。
avatar
c*g
8 楼
能否举个贪心不能解的set？
谢谢

【在 r****t 的大作中提到】
: 现实 coin set 贪心可解，对大部分假设的 coin set 贪心不能解，需要搜索回溯。
avatar
p*2
9 楼

第一道题，假设coin 是 90, 50, 1
给你100
如果用你的方法就会得到1个90,10个1,一共11个。 如果dp的话就是2个50.

【在 c***g 的大作中提到】
: 我在看DP问题的时候，碰到了两个题目，很是疑惑
: 1 给你一个整数，不同的coin，然后求最少多少个coin可以得到这个整数。
: 我的疑问是，这个题目需要DP么？假设coin 是1，3， 5， 给定17，直接先除以5，
: 然后剩下的除以3，然后剩下的除以1，不就行了么？这样的算法得到的答案有错误么？
: 2 给你一个整数数组，有正有负，求连续的数的最大的和。
: 这个题目不是有一个n的算法么？需要DP么？
: 谢谢了
: 。
avatar
r*n
10 楼
1 3 4
6
greedy: 4 1 1
optimal: 3 3

【在 c***g 的大作中提到】
: 能否举个贪心不能解的set？
: 谢谢
avatar
c*g
11 楼
谢谢，那如何判断什么时候用贪心，什么时候用DP呢？
或者是不是贪心会有不work的时候，但是DP一定work？
有没有什么情况贪心work，但是DP不work呢？

【在 p*****2 的大作中提到】
:
: 第一道题，假设coin 是 90, 50, 1
: 给你100
: 如果用你的方法就会得到1个90,10个1,一共11个。 如果dp的话就是2个50.
avatar
p*2
12 楼
第二道题什么意思呀？
avatar
p*2
13 楼

如果能证明贪心work就用贪心。不过很多时候看经验和感觉了。用贪心需要很小心，用
错的时候不少。如果能用DP，肯定DP保险。DP得到的一定是最优，应该不会有贪心work
，DP不work。当然前提是可以用DP。有些时候很难用DP来解，或者即使用DP，速度还是
慢，达不到要求。这种情况要不是DP用的不对，要不题目就应该用贪心来解。

【在 c***g 的大作中提到】
: 谢谢，那如何判断什么时候用贪心，什么时候用DP呢？
: 或者是不是贪心会有不work的时候，但是DP一定work？
: 有没有什么情况贪心work，但是DP不work呢？
avatar
p*2
14 楼

第二道题是我看错了，还是你改了。第二题用dp就是为了防止重复计算的。

【在 p*****2 的大作中提到】
: 第二道题什么意思呀？
avatar
c*g
15 楼
不好意思，是我改了。
请问这里重复计算指的是什么？

【在 p*****2 的大作中提到】
:
: 第二道题是我看错了，还是你改了。第二题用dp就是为了防止重复计算的。
avatar
p*2
16 楼

如果不用dp，要计算
f(i,j) sum from i to j
you have to sum them up, it takes time. imaging n is very large
using dp, it's just dp[j]-dp[i-1], very fast.

【在 c***g 的大作中提到】
: 不好意思，是我改了。
: 请问这里重复计算指的是什么？
avatar
p*2
17 楼
不好意思。又看错了。你提到O(n)的解法。
我认为这题O(n)的解法是好的。但是这也是一道典型的dp题。如果你在比赛中，用dp来
解比你用那个O(n)的要简单多了。如果面试中，就是考察那个O(n)的算法了。目的不一
样。
avatar
r*t
18 楼
牛人, 关于这个定理给个 reading 的 link 吧？

【在 r*******n 的大作中提到】
: 也不全对....对任何finite coin set...如果钱数足够大, 解一定是greedy的
: 但是这个门限要用DP来解
avatar
r*n
19 楼
我上个月准备onsite的时候随手写了个note, 但是mit不能传pdf附件

【在 r****t 的大作中提到】
: 牛人, 关于这个定理给个 reading 的 link 吧？
avatar
r*n
20 楼
刚想起来可以googledoc
https://docs.google.com/open?id=0B4h_
H60kAkxRZDViN2ZmZjUtZTgwZC00MTAzLTk3MDYtYjNjZmJiNzA4YmUw

【在 r****t 的大作中提到】
: 牛人, 关于这个定理给个 reading 的 link 吧？
avatar
g*e
21 楼

这题DP也是有O(n)解法的啊
max(i)=max sum of sub array ending at i
max(i+1)=MAX（max(i)+array[i+1], array[i+1])

【在 p*****2 的大作中提到】
: 不好意思。又看错了。你提到O(n)的解法。
: 我认为这题O(n)的解法是好的。但是这也是一道典型的dp题。如果你在比赛中，用dp来
: 解比你用那个O(n)的要简单多了。如果面试中，就是考察那个O(n)的算法了。目的不一
: 样。
avatar
q*x
22 楼

贪心法，应该有反例。dp经典题。
这个算不算dp两可。

【在 c***g 的大作中提到】
: 我在看DP问题的时候，碰到了两个题目，很是疑惑
: 1 给你一个整数，不同的coin，然后求最少多少个coin可以得到这个整数。
: 我的疑问是，这个题目需要DP么？假设coin 是1，3， 5， 给定17，直接先除以5，
: 然后剩下的除以3，然后剩下的除以1，不就行了么？这样的算法得到的答案有错误么？
: 2 给你一个整数数组，有正有负，求连续的数的最大的和。
: 这个题目不是有一个n的算法么？需要DP么？
: 谢谢了
: 。
avatar
p*2
23 楼

good.

【在 g*********e 的大作中提到】
:
: 这题DP也是有O(n)解法的啊
: max(i)=max sum of sub array ending at i
: max(i+1)=MAX（max(i)+array[i+1], array[i+1])
相关阅读
哈哈一笑 轻松愉快 Zz一个人拉屎的频率决定了 (转载)谁见过窦尔敦！ (转载)老刑气急败坏黔驴计穷地推出一个声优这位女神牛B吧无机点微笑：股事有风险，操股要小心数据plan (转载)FBI不起诉希拉里，是trump的一招妙棋令计划最后感谢法庭：“整个庭审庄重、严谨、理性、文明，体现(转载)喜欢谁就娶谁为什么说木星是太阳 系内最大的“情种” 科技日报 ugmbbc 1天1小时前 作为太阳系内最特殊的气态巨行星，木星一直以来都勾起了人们的无限遐想。据美国国家航空航天局（NASA）消息，“朱诺”号木星探测器历经5年旅程，终 于不辱使命，将于美国东部时间7月4日晚进入木星轨道，人类得以更近距离地与木星亲密接触。“块头”大、自转快、磁场强、大红斑最有名、自带光环、卫星 “情人”最多…… http://cms-bucket.nosdn.127.net/catchpic/f/f3/f3dc7a450779eb216ca02fbd43b7dfc5.jpg 作为太阳系内最特殊的气态巨行星，木星一直以来都勾起了人们的无限遐想。据美国国家航空航天局（NASA）消息，“朱诺”号木星探测器历经5年旅程，终于不辱使命，将于美国东部时间7月4日晚进入木星轨道，人类得以更近距离地与木星亲密接触。那么，木星究竟是一个什么样的存在，值得科学家们跨越数百年时间、跨越数亿万公里的空间，苦苦追寻呢? “块头”最大 据NASA官网介绍，木星是太阳系八大行星中体积最大、自转最快的行星，从内向外的第五颗行星。木星的赤道约为14.3万公里。木星如此大，太阳系内所有其他行星都能塞进木星里面，木星“大肚”能容超过1000颗行星。木星的质量是地球质量的318倍，是太阳系内所有其他行星质量总和的2.5倍。 木星距离太阳的平均距离是5.2个天文单位（1个天文单位为太阳与地球之间的距离，约为1.496亿千米），因此，其与太阳间的距离为地球与太阳之间距离的5倍多。当我们从地球上看时，它是夜空中亮度排第二的行星，排在“夜空中最亮行星”金星之后。 木星大气层由86%的氢气和14%的氦气组成。这颗行星的表面覆盖着厚厚的、棕黄色和白色相间的云层。 天文学家们将木星称为“失败的恒星”，但这一描述并不恰当。尽管有一点毋庸置疑：就像恒星一样，木星富含氢气和氦气，但木星的质量不足以在其内部触发核聚变反应。 http://cms-bucket.nosdn.127.net/catchpic/0/07/078c2139fc05dec95de910e44c7e56dc.jpg 自转最快 磁场最强 木星是太阳系内自转最快的行星。鉴于其大“块头”和傲视群雄的体重，木星的移动速度非常快。实际上，其自转速度为4.53万公里/小时（12.6公里/秒），一次自转只需10小时，因此，木星的一天只有10个小时。木星的轨道为椭圆或橄榄型，绕太阳旋转一次所需的时间是地球绕太阳旋转一次所需时间的12倍，因此，木星上的一年等于地球上的12年。 木星云层的温度约为零下145摄氏度。木星中央附近的温度非常高，核心温度约为2.4万摄氏度，比太阳表面还热。 如果一个人能站在木星大气层顶端，那么，它受到的引力约为在地球表面引力的2.4倍，因此，在地球上重100磅（约91斤）的人在木星上重达240磅（218斤）。 快速的旋转也助力木星获得了强大的磁场，木星拥有太阳系内最强大的磁场。在木星云层之下是一个巨大的液态金属氢组成的海洋。随着木星不断旋转，旋转的液态金属海洋制造出了这个强磁场，木星的磁场强度是地球磁场的2万多倍。 天文学家们认为，这一磁场会捕获源自木卫一上火山喷发的氧化硫粒子，这些氧化硫粒子与源自木星大气层的氢离子一起，在木星赤道面形成了一个磁层。 这一磁层与太阳风的交互作用会生成一个弓型冲击波，这是一个危险的辐射带，会破坏航天器。木星的四大卫星都在磁层内旋转，这会保护其远离太阳风的冲击，但是，也会使人们很难在这些卫星上建造前哨基地。 http://cms-bucket.nosdn.127.net/catchpic/e/e6/e68cb60f281e5c5f3de6b98c0da804c6.jpg 大红斑最有名 木星最引人注目的特征是其大红斑，它是一种反气旋风暴，位于木星赤道的南部，直径为2.4万千米，高度为1.2万到1.4万千米。在大红斑最宽的点，风暴大约是地球直径的3.5倍，足以容纳2到3个地球直径大小的行星。 木星是一个多风的行星，风力从192英里（309公里）/小时到超过400英里（644公里）/小时。 大红斑据信已经存在了至少360多年，1665年，意大利天文学家乔凡尼?卡西尼发现了它的存在。到20世纪，天文学家们开始认为，大红斑是一种风暴，由木星的湍流和快速运动的大气层造成。“旅行者1号”探测器证实了这一理论，1979年3月，“旅行者1”号在掠过该行星时，观测到了大红斑。 然而，大红斑显然一直在萎缩，根据“卡西尼”号的观测，在17世纪时，大红斑的大小为4万千米，几乎为目前的2倍。天文学家们并不知道是否或何时它将完全消失，但他们确信，另一个大红斑可能会出现在木星的某个地方。 自带光环 当人们想到有环的天体系统时，土星首先印入脑海。但实际上，天王星和木星也有自己的环。木星是第三个被发现有环的行星，因为其环极其暗淡。1979年，NASA的“旅行者1号”航天器发现木星有三个小环——最内层是由光晕粒子组成的环；中间是相当明亮的主环；外部是一个轻薄的类似薄纱的环。 科学家们普遍认为，这些环可能由其陨石撞击木星的卫星时，卫星喷射出的物质组成。实际上，主环被认为由来自木卫十五和木卫十六的物质组成；而薄纱环的物质来自木卫十四和木卫五。 http://cms-bucket.nosdn.127.net/catchpic/e/e2/e2464c5fa6006b79fcd4bdde61e61b47.jpg 肉眼可见 在大多数时候，木星不仅肉眼可见，还是全天第二亮星，在行星中仅次于金星，在所有天体中仅次于太阳、月亮和金星，居第四位，比太阳外的所有恒星都要亮得多。 不仅木星本身肉眼可见，在某些极端情况下，连木星的某些卫星都可以用肉眼看见。 “情人”最多（卫星最多） 目前，木星是太阳系拥有卫星数最多的行星，2012年2月23日科学家称发现了木星2颗新卫星，累计卫星达68颗。木星的英文名Juppiter（朱庇特）代表着古罗马神话中的众神之王，木星的卫星全部以朱庇特的情人命名。 按照距离木星的顺序，木星的四大“情人”分别为木卫一“依娥（lo）”、木卫二“欧罗巴（Europa）”、木卫三“伽倪墨得斯（Ganymede）”、木卫四 “卡利斯托（Callisto）”。这四颗卫星通常被称为“伽利略卫星”。伽利略发现，虽然木星在空中移动，但这些卫星仍环绕木星公转，从而得到支持哥白尼日心说的论据，即并非所有天体均环绕地球旋转。 木星最大的卫星是木卫三，它也是太阳系内最大的卫星，直径为5262千米。木卫三比水星还大，“块头”是火星的四分之三。木卫三是太阳系内唯一拥有自己磁场的卫星。木卫三和木卫四上有很多由冰块和岩石构成的环形山。 木卫一拥有很多活火山。这些火山产生了含硫的气体。木卫一橙黄色的表面很有可能由火山喷发出的硫组成。木卫二是“伽利略”卫星家族中最小的。木卫二的表面主要是水冰。冰下可能是水或冰组成的海洋，其含水量是地球的2倍。未名主编你可不能学天涯副主编啊Re: 要是真的女的喊停就得停 (转载)狗急跳墙，鸡呢？这个不错拼图姐，你来买买提，是想告诉自己，是幸福的滚我要批评河马了加州男子欲当街自杀 警察劝说无效 将其击毙中国足球羸弱，周恩来也有错，
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。