For this problem, greedy algo. works. Always choose the largest coin that is allowed. However,for some special sets of coins, such as 25, 10, 7, 5, 1, the greedy algo. doesn't work. So we need to use dynamical programming to solve this problem.
【在 c***2 的大作中提到】 : Given a list of coins such as 25, 10, 5, 1 : find the minimum number of coins for a target value such as 95.
f*o
5 楼
可以用
n*y
6 楼
有3G就不是这价了 我觉得没有sd是最大的败笔
y*m
7 楼
how about this 如果list很大,不要求subarray,就根据coin value 先找出对应的数字组合,从最小组 合开始对list搜索 如果要求subarray 就简单dp..
is greedy
【在 c**y 的大作中提到】 : For this problem, greedy algo. works. Always choose the largest coin that is : allowed. : However,for some special sets of coins, such as 25, 10, 7, 5, 1, the greedy : algo. doesn't work. So we need to use dynamical programming to solve this : problem.
RE this. Eventually we still need to find all possible combinations, then find min
is greedy
【在 c**y 的大作中提到】 : For this problem, greedy algo. works. Always choose the largest coin that is : allowed. : However,for some special sets of coins, such as 25, 10, 7, 5, 1, the greedy : algo. doesn't work. So we need to use dynamical programming to solve this : problem.