Golang每日一练(leetDay0110) 零钱兑换I\II Coin Change

简介: Golang每日一练(leetDay0110) 零钱兑换I\II Coin Change

322. 零钱兑换 Coin Change

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

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

示例 1:

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

输出:3

解释:11 = 5 + 5 + 1

示例 2:

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

输出:-1

示例 3:

输入:coins = [1], amount = 0

输出:0


提示:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2^31 - 1
  • 0 <= amount <= 10^4

代码:动态规划

状态方程: dp[0] = 0, dp[i] = min(dp[i], dp[i-coin]+1)

package main
import (
  "fmt"
  "math"
)
func coinChange(coins []int, amount int) int {
  dp := make([]int, amount+1)
  for i := 1; i <= amount; i++ {
    dp[i] = math.MaxInt32
    for _, coin := range coins {
      if i >= coin {
        dp[i] = min(dp[i], dp[i-coin]+1)
      }
    }
  }
  if dp[amount] == math.MaxInt32 {
    return -1
  }
  return dp[amount]
}
func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}
func main() {
  coins := []int{1, 2, 5}
  amout := 11
  fmt.Println(coinChange(coins, amout))
  coins = []int{2}
  amout = 3
  fmt.Println(coinChange(coins, amout))
  coins = []int{1}
  amout = 0
  fmt.Println(coinChange(coins, amout))
}

输出:

3

-1

0

注:创建一个长度为 amount+1 的一维数组 dp,并将 dp 中的所有元素初始化为一个非常大的数,这里我们使用了 math.MaxInt32。在循环遍历 dp 的过程中,对于每个 i,都遍历一遍硬币数组 coins,分别判断是否能使用每个硬币来凑出 i 元,如果可以,则使用当前的硬币更新 dp[i]。最后,如果 dp[amount] 仍然为一个非常大的数,说明无法凑出 amount 元,返回 -1,否则返回 dp[amount]。


518. 零钱兑换 II Coin Change ii

给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 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


提示:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

代码: 动态规划

状态方程: dp[0] = 1, dp[i] += dp[i-coin]

package main
import "fmt"
func change(coins []int, amount int) int {
  dp := make([]int, amount+1)
  dp[0] = 1
  for _, coin := range coins {
    for i := coin; i <= amount; i++ {
      dp[i] += dp[i-coin]
    }
  }
  return dp[amount]
}
func main() {
  coins := []int{1, 2, 5}
  amout := 5
  fmt.Println(change(coins, amout))
  coins = []int{2}
  amout = 3
  fmt.Println(change(coins, amout))
  coins = []int{10}
  amout = 10
  fmt.Println(change(coins, amout))
}

输出:

4

0

1

注:创建一个长度为 amount+1 的一维数组 dp,并将 dp[0] 初始化为 1。然后对于每个硬币 coin,都遍历一遍 dp 数组,计算出所有能够凑到的 i 元的硬币组合数,并且使用这些组合数更新 dp[i]。最后返回 dp[amount] 即可。


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/

Rust每日一练 专栏

(2023.5.16~)更新中...

Golang每日一练 专栏

(2023.3.11~)更新中...

Python每日一练 专栏

(2023.2.18~2023.5.18)暂停更

C/C++每日一练 专栏

(2023.2.18~2023.5.18)暂停更

Java每日一练 专栏

(2023.3.11~2023.5.18)暂停更


目录
相关文章
|
29天前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
46 0
Leetcode第21题(合并两个有序链表)
|
27天前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
80 0
|
2月前
|
机器学习/深度学习 数据处理 Python
从NumPy到Pandas:轻松转换Python数值库与数据处理利器
从NumPy到Pandas:轻松转换Python数值库与数据处理利器
66 0
|
3月前
|
Python
【Leetcode刷题Python】21. 合并两个有序链表
介绍了几种不同的方法来合并多个已排序的链表,包括暴力求解、使用小顶堆以及分而治之策略。
40 2
|
2月前
|
机器学习/深度学习 算法 数据可视化
8种数值变量的特征工程技术:利用Sklearn、Numpy和Python将数值转化为预测模型的有效特征
特征工程是机器学习流程中的关键步骤,通过将原始数据转换为更具意义的特征,增强模型对数据关系的理解能力。本文重点介绍处理数值变量的高级特征工程技术,包括归一化、多项式特征、FunctionTransformer、KBinsDiscretizer、对数变换、PowerTransformer、QuantileTransformer和PCA,旨在提升模型性能。这些技术能够揭示数据中的潜在模式、优化变量表示,并应对数据分布和内在特性带来的挑战,从而提高模型的稳健性和泛化能力。每种技术都有其独特优势,适用于不同类型的数据和问题。通过实验和验证选择最适合的变换方法至关重要。
43 5
8种数值变量的特征工程技术:利用Sklearn、Numpy和Python将数值转化为预测模型的有效特征
|
4月前
|
数据挖掘 Python
【Python】已解决:Python pandas读取Excel表格某些数值字段结果为NaN问题
【Python】已解决:Python pandas读取Excel表格某些数值字段结果为NaN问题
362 0
|
3月前
|
算法
LeetCode第21题合并两个有序链表
该文章介绍了 LeetCode 第 21 题合并两个有序链表的解法,通过创建新链表,依次比较两个链表的头节点值,将较小的值插入新链表,直至其中一个链表遍历完,再将另一个链表剩余部分接到新链表后面,实现合并。
LeetCode第21题合并两个有序链表
|
3月前
|
算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
|
3月前
|
Python
安装notepad++ 安装Python Python环境变量的数值。怎样在notepad++上运行Python的代码
这篇文章提供了在notepad++上安装和配置Python环境的详细步骤,包括安装Python、配置环境变量、在notepad++中设置Python语言和快捷编译方式,以及解决可能遇到的一些问题。
安装notepad++ 安装Python Python环境变量的数值。怎样在notepad++上运行Python的代码
|
4月前
【数据结构OJ题】合并两个有序链表
力扣题目——合并两个有序链表
39 8
【数据结构OJ题】合并两个有序链表