python动态规划-零钱兑换

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。

如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

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

输出: 3

解释: 11 = 5 + 5 + 1

示例 2:

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

输出: -1

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

from typing import List

class Solution:

    def coinChange(self, coins: List[int], amount: int) -> int:

        dp = [-1 for _ in range(amount+1)]

        dp[0]=0

        for i in range(len(coins)):

            if coins[i]<amount+1:

                dp[coins[i]] = 1

        for i in range(1,amount+1):

            temp = []

            for v in coins:

                if i-v>=0 and dp[i-v]!=-1:

                    temp.append(dp[i-v]+1)

            dp[i] = min(temp) if temp!=[] else -1

        return dp[amount]

if __name__ == "__main__":

    s= Solution()

    coins = [1, 2, 5]

    amount = 11

    # coins = [2]

    # amount = 3

    r= s.coinChange(coins, amount)

    print(r)

零钱兑换II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:

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

输出: 4

解释: 有四种方式可以凑成总金额:

5=5

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

示例 2:

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

输出: 0

解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10, coins = [10]

输出: 1

from typing import List

class Solution:

    def change(self, amount: int, coins: List[int]) -> int:

        dp = [0 for _ in range(amount+1)]

        dp[0] = 1

        for value in coins:

            for i in range(amount+1):

                if i-value>=0:

                    dp[i] +=dp[i-value]

        return dp[amount]