322_零钱兑换-python

概述动态规划问题，稍后更新思路 class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ INF = float(

动态规划问题，稍后更新思路

class Solution(object):    def coinChange(self,coins,amount):        """        :type coins: List[int]        :type amount: int        :rtype: int        """        INF = float('inf')        dp = []        N = len(coins)        for _ in range(N):            tmp = [INF] * (amount+1)            tmp[0] = 0            dp.append(tmp)        for j in range(1,amount+1):            if j >= coins[0] and dp[0][j-coins[0]] != INF:                dp[0][j] = dp[0][j-coins[0]] + 1        for i in range(1,N):            for j in range(1,amount+1):                if j >= coins[i]:                    dp[i][j] = min(dp[i - 1][j],dp[i][j-coins[i]] + 1)                else:                    dp[i][j] = dp[i - 1][j]        return dp[len(coins)- 1][amount] if dp[N-1][amount] != INF else -1

总结

以上是内存溢出为你收集整理的322_零钱兑换-python全部内容，希望文章能够帮你解决322_零钱兑换-python所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。