LeetCode 322. Coin Change

Description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3

Output: -1

Note:

You may assume that you have an infinite number of each kind of coin.

描述

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

示例 1:

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

输出: 3

解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3

输出: -1

说明:

你可以认为每种硬币的数量是无限的。

思路

• 这道题目使用动态规划。
• 对于要兑换面值为 a 的硬币，我们从面值为 0 的硬币开始找，一路规划到 a。
• 状态：matrix[i][j],表示使用 coins 的前 i 个硬币，兑换面值为 j 的硬币所需要的硬币的个数。
• 状态转移：
• 对于面值的 k 的硬币，假设此时我们已经使用了 coins 的前 i 个银币，则
• 1.我们可以把 k 拆分成 k - coins[i] + coins[i]，即需要面值为 k - coins[i] 的硬币需要兑换的硬币个数 + 1；
• 2.我们也可以不使用当前的硬币，那么兑换面值为 k 的硬币就需要使用前 i-1 个硬币兑换面值为 k 的硬币的个数；
• 我们取出上面两种情况的最小值。
• 结果：矩阵的最后一个值。

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-03-01 10:21:19
# @Last Modified by:   何睿
# @Last Modified time: 2019-03-01 14:33:42


class Solution:
    def coinChange(self, coins: [int], amount: int) -> int:
        # 声明一个二维矩阵
        matrix = [[i for i in range(amount + 1)] for _ in range(2)]
        # 初始化第一行
        for i in range(amount + 1):
            # 如果当前位置表示的需要兑换的钱数可以被整除，将当前位置置为需要钱的个数
            if i % coins[0] == 0:
                matrix[0][i] = i // coins[0]
            # 否则将当前的钱数目置为 amount+1
            else:
                matrix[0][i] = amount + 1
        for i in range(1, len(coins)):
            for j in range(amount + 1):
                row = i % 2
                # 不使用第 i 个硬币，仅使用 i 前面的所有硬币
                # 则一共需要当前行上一行对应位置的硬币
                top = matrix[(i - 1) % 2][j]
                # 使用当前的硬币，如果当前需要兑换的硬币面值大于当前硬币的面值
                if j >= coins[i]:
                    # 动态规划：兑换面值为 a 的硬币，在已经使用了coins[0:col-1]这些硬币的情况下
                    # 可以由 a - coins[col] 需要的硬币加上硬币 coins[col]，
                    # 所以需要的硬币个数为 matrix[row][a - coins[col]]+1；
                    # 也可以不使用当前的硬币，仅仅使用前 i 个硬币
                    # 那么需要的硬币个数为 matrix[row-1][col]
                    # 取出最下值
                    matrix[row][j] = min(top, matrix[row][j - coins[i]] + 1)
                else:
                    matrix[i % 2][j] = top
        res = 0
        # 为了节省空间，我们的矩阵仅仅使用了两行，
        # 如果 coins 的个数为奇数个，那么最终结果在第一行
        if len(coins) % 2:
            res = -1 if matrix[0][-1] == amount + 1 else matrix[0][-1]
        # 如果 coins 的个位数为偶数个，那么最终结果为第二行
        else:
            res = -1 if matrix[1][-1] == amount + 1 else matrix[1][-1]
        return res

    def coinChange2(self, coins: [int], amount: int) -> int:
        # 思路同方法一完全一样，仅仅是换了一种写的方式
        # python 对于列表解析式的执行效率更快
        count = amount + 1
        line = [i for i in range(count)]
        for i in range(1, count):
            line[i] = min(line[i - c] if i >= c else count for c in coins)
            if line[i] != count: line[i] += 1
        return line[-1] if line[-1] != count else -1

源代码文件在 这里 。

©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明.

微信公众号：techruicore