322. Coin Change
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
Approach #1 (Brute force) [Time Limit Exceeded]
上面的问题可以建模成如下的最优化问题:
其中$S$是总额,$c{i}$是第$i$种硬币,$x{i}$是第$i$种硬币$c{i}$在找零$S$的数量。很容易得出判断$x{i} = [0,\frac{S}{c_{i}}]$.
贪心算法每次会选取可能的最大面值来实现硬币总数最少。(并不能保证找出最优解。)
Approach #2 (Dynamic programming - Top down) [Accepted]
假设$F(S)$表示找零$S$元需要的最少硬币数
Approach #3 (Dynamic programming - Bottom up) [Accepted]
1 | int coinChange(vector<int> &coins, int amount) |
https://forum.letstalkalgorithms.com/t/coin-change-leetcode/394