labuladong
动态规划详解 :: labuladong的算法小抄
首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。——这里为何是2^n? 子问题不是只有n个吗
凑零钱问题。最少几枚硬币，肯定是先尽量用最大面值的凑，如果剩余的钱数凑不开，就减一个最大面值的，我写了这样一个算法,输入的硬币列表要先排序,想知道这个算动态规划么：
def coinChange(coins, amount):
def dp(coins, amount):
if amount == 0:
return 0
if len(coins) == 0:
return -1
bigest_coin = coins[0]
other_coins = coins[1:]
count_bigestcoin = amount // bigest_coin
while count_bigestcoin >= 0:
submin = dp(other_coins, (amount - count_bigestcoin * bigest_coin))
if submin != -1:
return count_bigestcoin + submin
count_bigestcoin -= 1
return -1
return dp(coins, amount)
coins = [3,7]
amount = 21
coins.sort(reverse=True)
print( coinChange(coins, amount))
@tinyhare 回复楼上老哥的疑问 楼上老哥的说法应该是贪心算法，我一看题也觉得可以贪心好，简单直接，但这道题贪心不一定有解。 假如coins=[3,11], amoutn=12, 那么根据贪心策略，优先选择11面值硬币，此时amount=12-11=1，即还有一块钱没法找开，按楼上老哥的说法没法找开就减去一个最大面值即：1-12=-11,还是找不开； 但如果用穷举策略，可以穷举出12=3+3+3+3，即用4个3元硬币可以找开，所以贪心不一定有解的情况，穷举可能有解
public static int coinChange(int[] coins, int amount) { if(amount == 0 ) { return 0; } if(amount < 0 ) { return -1; } int res = Integer.MAX_VALUE; for (int i = 0 ;i < coins.length ; i++) { int i1 = coinChange(coins, amount - coins[i]); if (i1 == -1){ continue; } res = Math.min(res,i1 + 1); } return res == Integer.MAX_VALUE ? -1 : res; } 这个超时了在力扣上面
@maozhida 回复老哥 “就减去一个最大面值即：1-12=-11” 我的意思不是这样减，还是coins=[3,11], amoutn=12 首先，尝试最多数量的11，即一个11，此时 12 - 111 余1，余数1用3来凑，无法配出来，所以11的数量要减一个，即0个11。 然后12 - 110 余 12， 然后余数12用3来凑，恰好就得到了结果。
这种算法是贪心算法啊，刚学算法不懂，谢谢指出。