wywwzjj's Blog.

Leetcode 322.Coin Change[DP]

字数统计: 298阅读时长: 1 min
2019/04/04 Share

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1

示例 1:

1
2
3
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

1
2
输入: coins = [2], amount = 3
输出: -1

分析

考虑状态方程,需描述出组合成总金额所花最少的硬币个数。

1
2
3
4
5
6
# dp[i][j] 表示使用前 i 种硬币表示总额 j 所用的最少硬币数
# 初始状态 dp[-1][j] = ∞ dp[i][0] = 0
dp[i][j] = min(dp[i][j], dp[i-1][j-coin_i*k] + k)
= min(dp[i][j], dp[i][j-coin_i] + 1)
# 观察发现都具有 dp[i],进一步压缩,使用滚动数组
dp[j] = min(dp[j], dp[j-coin_i] + 1)

以*示例 1 *为例

code

DP

1
2
3
4
5
6
7
8
9
# 执行用时:1672 ms,击败了 39.85% 的用户
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount+1] * (amount + 5)
dp[0] = 0
for coin in coins:
for i in range(amount+1):
if (i - coin >= 0):
dp[i] = min(dp[i], dp[i-coin] + 1)
return -1 if dp[amount] >= amount + 1 else dp[amount]

DFS + greedy + pruning

待补充

CATALOG
  1. 1. 题目描述
  2. 2. 分析
  3. 3. code