由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 关于DP的问题
相关主题
说说某著名软件公司的onsite面试问一道古老的面试题
请教算法: 三等分石子 (转载)问一个老题目
关于什么时候可以用贪心算法求找零问题Google面试怎么这么难啊,LG很难过,我该怎么劝他呢? (转载)
给定整数数组和两个整数的和,求所有pair。请教一道题
问一道面试题亚马逊电话第二轮
Target coins求函数的极值那题的解法?
找零钱dp的问题程序员的思维太牛逼了 (转载)
问道硬币题目回报本版A-M-G面巾
相关话题的讨论汇总
话题: dp话题: coin话题: 贪心话题: max
进入JobHunting版参与讨论
1 (共1页)
c***g
发帖数: 472
1
我在看DP问题的时候,碰到了两个题目,很是疑惑
1 给你一个整数,不同的coin,然后求最少多少个coin可以得到这个整数。
我的疑问是,这个题目需要DP么?假设coin 是1,3, 5, 给定17,直接先除以5,
然后剩下的除以3,然后剩下的除以1,不就行了么?这样的算法得到的答案有错误么?
2 给你一个整数数组,有正有负,求连续的数的最大的和。
这个题目不是有一个n的算法么?需要DP么?
谢谢了
r****t
发帖数: 10904
2
现实 coin set 贪心可解,对大部分假设的 coin set 贪心不能解,需要搜索回溯。

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

r*******n
发帖数: 266
3
也不全对....对任何finite coin set...如果钱数足够大, 解一定是greedy的
但是这个门限要用DP来解

【在 r****t 的大作中提到】
: 现实 coin set 贪心可解,对大部分假设的 coin set 贪心不能解,需要搜索回溯。
c***g
发帖数: 472
4
能否举个贪心不能解的set?
谢谢

【在 r****t 的大作中提到】
: 现实 coin set 贪心可解,对大部分假设的 coin set 贪心不能解,需要搜索回溯。
p*****2
发帖数: 21240
5

第一道题,假设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么?
: 谢谢了
: 。

r*******n
发帖数: 266
6
1 3 4
6
greedy: 4 1 1
optimal: 3 3

【在 c***g 的大作中提到】
: 能否举个贪心不能解的set?
: 谢谢

c***g
发帖数: 472
7
谢谢,那如何判断什么时候用贪心,什么时候用DP呢?
或者是不是贪心会有不work的时候,但是DP一定work?
有没有什么情况贪心work,但是DP不work呢?

【在 p*****2 的大作中提到】
:
: 第一道题,假设coin 是 90, 50, 1
: 给你100
: 如果用你的方法就会得到1个90,10个1,一共11个。 如果dp的话就是2个50.

p*****2
发帖数: 21240
8
第二道题什么意思呀?
p*****2
发帖数: 21240
9

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

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

p*****2
发帖数: 21240
10

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

【在 p*****2 的大作中提到】
: 第二道题什么意思呀?
相关主题
Target coins问一道古老的面试题
找零钱dp的问题问一个老题目
问道硬币题目Google面试怎么这么难啊,LG很难过,我该怎么劝他呢? (转载)
进入JobHunting版参与讨论
c***g
发帖数: 472
11
不好意思,是我改了。
请问这里重复计算指的是什么?

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

p*****2
发帖数: 21240
12

如果不用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 的大作中提到】
: 不好意思,是我改了。
: 请问这里重复计算指的是什么?

p*****2
发帖数: 21240
13
不好意思。又看错了。你提到O(n)的解法。
我认为这题O(n)的解法是好的。但是这也是一道典型的dp题。如果你在比赛中,用dp来
解比你用那个O(n)的要简单多了。如果面试中,就是考察那个O(n)的算法了。目的不一
样。
r****t
发帖数: 10904
14
牛人, 关于这个定理给个 reading 的 link 吧?

【在 r*******n 的大作中提到】
: 也不全对....对任何finite coin set...如果钱数足够大, 解一定是greedy的
: 但是这个门限要用DP来解

r*******n
发帖数: 266
15
我上个月准备onsite的时候随手写了个note, 但是mit不能传pdf附件

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

【在 r****t 的大作中提到】
: 牛人, 关于这个定理给个 reading 的 link 吧?
g*********e
发帖数: 14401
17

这题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)的算法了。目的不一
: 样。

q****x
发帖数: 7404
18

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

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

p*****2
发帖数: 21240
19

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])

1 (共1页)
进入JobHunting版参与讨论
相关主题
回报本版A-M-G面巾问一道面试题
湾区某职业社交网络公司电话一面Target coins
CC 10.3 的follow up的解法是不是有问题?找零钱dp的问题
计算expression的函数问道硬币题目
说说某著名软件公司的onsite面试问一道古老的面试题
请教算法: 三等分石子 (转载)问一个老题目
关于什么时候可以用贪心算法求找零问题Google面试怎么这么难啊,LG很难过,我该怎么劝他呢? (转载)
给定整数数组和两个整数的和,求所有pair。请教一道题
相关话题的讨论汇总
话题: dp话题: coin话题: 贪心话题: max