您当前位置：首页 > php开源 > php教程 > 【Leetcode】Coin Change

【Leetcode】Coin Change

来源：程序员人生发布时间：2016-06-08 13:01:56 阅读次数：2203次

题目链接：https://leetcode.com/problems/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 ⑴.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

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

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

思路：

c[i]表示数目为i时最少需要多少个硬币。

算法：

public int coinChange(int[] coins, int amount) { int c[] = new int[amount + 1]; for (int i = 1; i <= amount; i++) { int min = ⑴; for (int j = 0; j < coins.length; j++) { if (i - coins[j] >= 0 && c[i - coins[j]] != ⑴){ if(min==⑴){//当第1次判断时 min = c[i-coins[j]]+1; }else{ min = Math.min(min, c[i - coins[j]] + 1); } } } c[i] = min; } return c[amount] ; }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 MyBatis 3.4.0 版本功能介绍

下一篇 【MongoDB】window环境下MongoDB64位安装

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点