换钱的最少货币数

发表于

这是我参与11月更文挑战的第20天，活动详情查看：2021最后一次更文挑战

换钱的最少货币数

问题描述

322. 零钱兑换

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。如果无解，请返回-1.

示例：

输入：coins = [1, 2, 5]，amount = 11

输出：3

说明：11 = 5 + 5 + 1

分析问题

由于题目是求最优解问题，所以我们最直观的感觉就是这题是否可以使用动态规划来求解。

我们都知道，对于求解动态规划相关的问题，最重要的就是求出状态转移方程。下面我们来看一下如何求解，首先我们定义F(S) 为组成金额 S 所需的最少货币数量。

假设目前我们已经知道了F(S)，和最后一枚货币的面值是C，我们就可以得出:

F(S)=F(S-C)+1
由于最后一枚货币的面值是未知的，所以我们需要枚举每个货币的面额值 C0， C1，…..，Cn-1，并选择其中的最小值。即

F(S)=min {F(S-C0) ，F(S-C1)，F(S-C3)，….，F(S-Cn-1)} + 1

S-Ci >=0
当S=0时，F(S)=0
当n=0时，即货币的种类为0时，F(S)无解，即F(S)=-1
所以，F(S)的状态转移方程为

F(S)=min {F(S-C0) ，F(S-C1)，F(S-C3)，….，F(S-Cn-1)} + 1
其中 Cj 代表的是第 j 枚货币的面值，即我们枚举最后一枚货币面额是Cj，那么F(S)需要从S-Cj这个金额对应的状态 F(S-Cj) 转移过来，再加上枚举的这枚货币数量1的贡献。由于题目是求货币的数量最少，所以 F(S)为前面能转移过来的状态的最小值。

假设 coins= [1, 2, 5]，amount = 11，即F(11) = min( F(10), F(9), F(6) ) + 1。

image-20211118171456070

下面我们来看一下代码的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
ini复制代码import sys
class Solution:
    def coinChange(self, coins,amount):
        dp = [sys.maxsize] * (amount + 1)

        #S为0时，需要的货币数为0
        #S<0时，直接忽略dp[S]
        dp[0] = 0
        for coin in coins:
            #忽略S<0的。
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != sys.maxsize else -1

该算法的时间复杂度是O(Sn)，其中S是金额数，n是不同面额的个数。空间复杂度是O(S)。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%