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 | |
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 的大作中提到】
: 第二道题什么意思呀？
|
|
|
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])
|
