文章目录

题目思路1.确定`dp`函数（数组）的定义2.确定「状态转移方程」3.确定基本情况4.大概思路 代码暴力递归（自上而下）递归 + 备忘录（自上而下）使用dp 数组迭代（自下而上）

题目

题目传送：这里

思路

因为硬币的数量是没有限制的，子问题之间没有相互制，是互相独立的。具有「最优子结构」

所以可以判断，这个问题是看作是动态规划问题。

接下来就是动态规划三步走。

1.确定dp函数（数组）的定义

函数 dp(n)表示，当前的目标金额是n，至少需要dp(n)个硬币凑出该金额。

2.确定「状态转移方程」

能凑出硬币

很明显，在选择一枚硬币后，dp(n) = min(无限大, 1 + dp(n - 这次选择的硬币的值))。

当然这里不一当要用无限大来表示，可以用amount+1来替代。

为什么呢？因为凑9块钱最多要用9个1块钱硬币，所以10就可以当做凑硬币所用硬币数达不到的上限了。

凑不出硬币

dp(n) = -1

根据以上信息，写出大概框架如下

def coinChange(coins: List[int], amount: int): # 要凑出金额 n，至少要 dp(n) 个硬币 def dp(n): # 做选择，需要硬币最少的那个结果就是答案 for coin in coins: res = min(res, 1 + dp(n - coin)) return res return dp(amount)

3.确定基本情况

目标金额为 0 时，所需硬币数量为 0；

硬币金额正好等于目标金额时，结果为1；

硬币金额大于目标金额时，跳过；

当目标金额小于 0 时，无解，返回 -1。

4.大概思路

既然如此，可以从自顶向下和自底向上两个方向来考虑。

自上而下的思路主要是从树状的角度来考虑，每一次选择都是一次分支，一直计算到基本解，然后再迭代回溯。

自底向上就是从基本解开始，一步步往后推。好了，直接上代码吧。

代码

暴力递归（自上而下）

这个应该很好理解，不多说了。

def coinChange(coins: List[int], amount: int): def dp(n): # base case if n == 0: return 0 if n < 0: return -1 # 求最小值，所以初始化为正无穷 res = float('INF') for coin in coins: subproblem = dp(n - coin) # 子问题无解，跳过 if subproblem == -1: continue res = min(res, 1 + subproblem) return res if res != float('INF') else -1 return dp(amount)

递归 + 备忘录（自上而下）

引入备忘录，避免重复计算子问题。

子问题数目为 O(n)。处理一个子问题的时间不变，仍是 O(k)，总的时间复杂度是 O(kn)。

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: memo = dict() def dp(n): if n in memo: return memo[n] if n == 0: return 0 if n < 0: return -1 # 无限多个硬币 res = float("INF") for coin in coins: subproblem = dp(n-coin) if(subproblem == -1): continue res = min(res, 1 + subproblem) memo[n] = res if res != float("INF") else -1 return memo[n] return dp(amount)

使用dp 数组迭代（自下而上）

时间复杂度：O(Sn)，其中 S 是金额，n 是面额数。一共需要计算 O(S) 个状态，S 为题目所给的总金额。对于每个状态，每次需要枚举 n 个面额来转移状态，所以一共需要 O(Sn)的时间复杂度。空间复杂度：O(S)。DP 数组需要开长度为总金额 S 的空间。 public class Solution { public int coinChange(int[] coins, int amount) { // 数组大小为 amount + 1，初始值也为 amount + 1 int[] dp = new int[amount + 1]; // 凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币） for (int i = 1; i <= dp.length - 1; i++) { dp[i] = amount + 1; } for (int i = 0; i <= dp.length - 1; i++) { for (int coin : coins) { // 一个硬币的值就超过了要凑的钱 if (i < coin) { continue; } if(i == coin){ dp[i] = 1; } dp[i] = Math.min(dp[i], 1 + dp[i - coin]); } } return (dp[amount] == amount + 1) ? -1 : dp[amount]; } }