题目描述
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1
。
示例 1:
输入: coins = [1, 2, 5], amount = 11 |
示例 2:
输入: coins = [2], amount = 3 |
分析
考虑状态方程,需描述出组合成总金额所花最少的硬币个数。
# dp[i][j] 表示使用前 i 种硬币表示总额 j 所用的最少硬币数 |
以*示例 1 *为例
code
DP
# 执行用时:1672 ms,击败了 39.85% 的用户 |
DFS + greedy + pruning
待补充
- By:wywwzjj.top
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论