动态规划之零钱兑换_请设计一个 o(nv) 的动态规划算法,判断能否兑换金额 v。

前面以最大背包问题为例，总结了动态规划题目的解题套路。这次我们就按照套路模板，再来剖析一道经典动规题目——零钱兑换。

问题描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

问题分析

考察其是否满足动态规划的两个特征：

• 是否求最值？显而易见，这是一个求最小值的问题；
• 是否具有最优子结构？考察大规模问题的解是否可以由小规模问题的解推导出来。我们可以假设amount<n所需的最小硬币数量都是已知的，那如何得出amount=n所需的最小硬币数量呢？可以结合具体场景，如果你手上有1块、2块面额的硬币，要求凑出总额amount =5的所需最小硬币个数，而amount <5的所需最小硬币个数是已知的。很容易想到，只需要在amount =3或者amount =4的所需最小硬币个数的基础上再加1个硬币（2块或者1块）就可以得到amount =5所需的硬币个数了（注意，这里还不是最小硬币个数），再取这两种情况的最小值，便可以得到amount =5的所需的最小硬币个数了（是不是想起了跳台阶问题？）。

以上分析我们可以得出，该问题是动态规划问题。

求解套路

• 明确有哪些状态。很容易想到，在状态转化过程（大规模问题由小问题规模问题推导的过程）中，总金额amount 一定是发生变化的，因此amount 是状态。

• 明确dp数组含义。根据求什么设什么原则，我们可以设dp代表最少硬币数量，由于只有amount一个状态，因此dp为1维。综上，dp应设为dp[n]，代表凑出总额为n需要的最少数量金币。

• 状态转移方程。有了【问题分析】中的例子，相信找出状态转移方程并不难，直接贴结论：

  $dp[n]={\min }_{coin\in coins}(dp[n-coin])+1$

• 初始化dp。由于求的是最小值，因此要反着来，初始化为最大。考虑到coins是正整数数组，即coin最小是1，所以对于总金额n，最坏情况下（即只用面值为1的硬币）需要n个硬币。我们需要将dp初始化为正常情况下取不到的值，因此我们将dp其初始化为n+1。

代码

‘’’

def coin_change(coins,amount):

    # 判断边界值
    if amount == 0:
        return 0

    # 初始化dp数组，长度是amount+1，因为0~n一共有n+1个元素
    dp = [amount+1]*(amount+1)
    # 因为dp[n]要靠dp[0]推导，所以dp[0]需要按实际情况初始化为0
    dp[0] = 0

    # 遍历状态
    for i in range(1,amount+1):
        # 注意coins并不是状态，只是我们状态转移方程需要遍历它取最小值
        for coin in coins:
            if i-coin >= 0:
                dp[i] = min(dp[i],dp[i-coin]+1)
    if dp[amount] == amount+1: # 若为真，说明无解
        return -1
    else:
        return dp[amount]


if __name__ == '__main__':
	
    # 测试用例，来自leecode #322题
    eg =[[[1,2,5],11],[[2],3],[[1],0],[[1],1],[[1],2]]
    for coins,amount in eg:
        print(coin_change(coins,amount),end='  ')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

算法复杂度分析

• 时间复杂度

  显然是O(nm)，其中n为amount，即总金额，m为硬币coins的种类。

• 空间复杂度

  由于我们使用长度为amount+1的数组dp来保存状态，因此为O(n)。

欢迎关注公众号：