[LeetCode - Dynamic Programming] Coin Change

dackel 发布于2019-08-16 10:26 / 2762人阅读

摘要：解题思路动态规划，用表示总价为的最小纸币张数，很容易想到状态转移方程当然前提是要大于纸币金额数。表示取一张面额加上合计为的最小纸币数。另题目要求无法合计出的金额，要返回，所以要作特殊处理，否则就会返回元素初始化值代码

Coin Change
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:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

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

1.解题思路
动态规划，用dp[i]表示总价为i的最小纸币张数，很容易想到状态转移方程:
dp[i]=Math.min(dp[i-coins[0]]+1,dp[i-coins[1]]+1,...,dp[i-coins[n-1]]+1),当然前提是i要大于纸币金额数。
dp[i-coins[0]]+1: 表示取一张coins[0]面额加上合计为i-coins[0]的最小纸币数。
另题目要求无法合计出的金额i，dp[i]要返回-1，所以要作特殊处理，否则就会返回元素初始化值0.

2.代码

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins.length==0) return -1;
        if(amount==0) return 0;
        int[] dp=new int[amount+1]; //start from 1, intead of 0
        for(int i=1;i<=amount;i++){
            int minNumber=Integer.MAX_VALUE;
            for(int j=0;j=coins[j]&&dp[i-coins[j]]!=-1){
                    minNumber=Math.min(dp[i-coins[j]]+1,minNumber);
                }
            }
            dp[i]=minNumber==Integer.MAX_VALUE?-1:minNumber;
        }
        return dp[amount];
    }
}

GPU云服务器云服务器 dynamic-programming Coin coin 域名行情 change

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69795.html

leetcode322. Coin Change

摘要：传入的参数为手上有的纸币的面额以及希望兑换的面额。这里假设纸币的数量是无穷的。这题本质上考察的是动态规划思想。这里有两种动态规划的方法，分别从递归和非递归的角度解决这个问题。具体的情况还是要看数据的分布情况来确定选择哪种方法。题目要求 You are given coins of different denominations and a total amount of money ...

kohoh_ 2019-08-15 14:41 评论0 收藏0
[LeetCode] 322. Coin Change

Problem 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 o...

ccj659 2019-08-16 13:37 评论0 收藏0
[LeetCode] 518. Coin Change 2

Problem You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infini...

stefan 2019-08-16 13:44 评论0 收藏0
[Leetcode-Dynamic Programming]Unique Binary Search

Unique Binary Search TreesGiven n, how many structurally unique BSTs (binary search trees) that store values 1...n? For example,Given n = 3, there are a total of 5 unique BSTs. 1 3 3 ...

MartinDai 2019-08-16 10:27 评论0 收藏0
[Leetcode- Dynamic Programming] Best Time to Buy a

摘要：代码解体思路依然是动态规划，寻找状态，因为本题涉及到，所以第天的状态我们分为持股和未持股，即维护两个数组，和分别表示第天持股和未持股所获得的最大收益。 Best Time to Buy and Sell Stock Say you have an array for which the ith element is the price of a given stock on day...

hiyayiji 2019-08-14 16:41 评论0 收藏0