兑换零钱(一)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
 
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        if len(arr) == 0:

            return -1
        dp = [aim+1] * (aim+1)
        dp[0] =  0

        for i in range(len(arr)):
            for j in range(arr[i], aim+1):
                dp[j] = min(dp[j-arr[i]]+1, dp[j])
        if dp[aim] == aim+1:
            return -1
        return dp[aim]

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        dp = [aim+1 for _ in range(aim+1)]
        dp[0] = 0  
        for i in range(1, aim + 1):
            for coin in arr:
                if i - coin >=0:
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        return dp[aim] if dp[aim] != aim+1 else -1

这个问题是一个典型的动态规划问题，也被称为“完全背包问题”。我们可以使用动态规划来求解组成给定钱数aim所需的最少货币数。

首先，我们定义一个数组dp，其中dp[i]表示组成钱数i所需的最少货币数。初始时，我们将dp数组的所有元素都设置为一个较大的数（比如aim + 1），表示初始状态下无法组成任何钱数。然后，我们将dp[0]设置为0，表示组成钱数0不需要任何货币。

接下来，我们遍历数组arr中的每个货币面值，对于每个面值，我们再次遍历dp数组，从该面值开始，更新每个钱数所需的最少货币数。具体的更新方式是：如果当前钱数i可以由之前的某个钱数j（j < i）加上当前面值得到，并且使用当前面值组成钱数i所需的货币数比之前的更少，那么我们就更新dp[i]。

最后，我们检查dp[aim]的值，如果它仍然是我们初始设置的那个较大的数，说明无法组成钱数aim，返回-1；否则，返回dp[aim]作为结果。

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        dp = [aim + 1] * (aim + 1)  
        dp[0] = 0  

        for coin in arr:  
            for i in range(coin, aim + 1):  
                dp[i] = min(dp[i], dp[i - coin] + 1)  

        return dp[aim] if dp[aim] != aim + 1 else -1

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        dp = [aim+1]*(aim+1)
        dp[0]=0
        for i in range(1,aim+1):
            for j in arr:
                if j>i:
                    continue
                dp[i] = min(dp[i],dp[i-j]+1)
        return dp[aim] if dp[aim]!=aim+1 else -1

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # 定义a[i]为组成i的最少货币数
        # 状态转移矩阵a[i] = min(a[i-arr[0]], a[i-arr[n]]) + 1
        # 输出值a[aim]
        # 边界条件： a[i]全部初始化为0即可

        a = [0] * (aim + 1)
        for i in range(1, aim+1):
            min_num = 9999
            for coin in arr:
                if i >= coin:
                    min_num = min(min_num, a[i-coin] + 1)
            a[i] = min_num
        return a[aim] if a[aim] < 9999 else -1

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        tmp = [-1 for i  in range(aim+1)]
        tmp[0] = 0
        for i in range(1, aim+1):
            for j in arr:
                if i - j == 0:
                    tmp[i] = 1
                elif i - j > 0 and tmp[i-j] > 0:
                    if tmp[i] == -1:
                        tmp[i] = tmp[i - j] + 1
                    else:
                        tmp[i] = min(tmp[i], tmp[i-j] + 1)
        return tmp[aim]

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        if aim < 1:
            return 0 
        dp = [(aim + 1) for i in range(aim + 1)]  ## 确定 dp , 因为要求 min 所以初始化可以用最大值 + 1完成定义 
        dp[0] = 0   ## 初始化情况， 当aim = 0时候，dp 也为 0 
        for i in range(len(arr)):    ## 遍历 arr   （遍历物品）
            for j in range(arr[i], aim+1):  ## 遍历剩下的空间 （遍历背包）
                dp[j] = min(dp[j], dp[j-arr[i]] + 1)  ## 当前容量，和 待更新容量取出最小值 
        if dp[aim] > aim:
            return -1 
        else:
            return dp[aim]