Java剑指 Offer II 103. 最少的硬币数目（击败83.77%用户）

本文主要是介绍Java剑指 Offer II 103. 最少的硬币数目（击败83.77%用户），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：

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

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

示例 :

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

思路：

很像之前写的题目，但是完全不像，也有点像，坑有点多

把三角形变成直角三角形最好理解

[2]

[3,4]

[6,5,7]

[4,1,8,3]

像这样

剩下的看代码注释

复杂度：

时间：双重循环O（nt）。

空间：O（t）。

代码：

    public int coinChange(int[] coins, int amount) {
        //背包问题不是01背包
        //dp[i]记录完成i数目组合数
        int dp[] = new int[amount+1];
        for(int i = 1;i<=amount;++i){
            dp[i] = amount +1;
          for(int coin :coins){
              if(i>=coin){
                dp[i] = Math.min(dp[i],dp[i-coin] +1);
              }
          }
        }
        return dp[amount] > amount? -1:dp[amount];
    }

这篇关于Java剑指 Offer II 103. 最少的硬币数目（击败83.77%用户）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！