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)暂停更


目录
相关文章
|
1月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
48 0
Leetcode第21题(合并两个有序链表)
|
1月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
88 0
|
26天前
|
存储 Python
[oeasy]python038_ range函数_大小写字母的起止范围_start_stop
本文介绍了Python中`range`函数的使用方法及其在生成大小写字母序号范围时的应用。通过示例展示了如何利用`range`和`for`循环输出指定范围内的数字,重点讲解了小写和大写字母对应的ASCII码值范围,并解释了`range`函数的参数(start, stop)以及为何不包括stop值的原因。最后,文章留下了关于为何`range`不包含stop值的问题,留待下一次讨论。
19 1
|
2月前
|
Python
6-18|Python画字母H
6-18|Python画字母H
|
3月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
27 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
3月前
|
算法
LeetCode第21题合并两个有序链表
该文章介绍了 LeetCode 第 21 题合并两个有序链表的解法,通过创建新链表,依次比较两个链表的头节点值,将较小的值插入新链表,直至其中一个链表遍历完,再将另一个链表剩余部分接到新链表后面,实现合并。
LeetCode第21题合并两个有序链表
|
3月前
|
算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
【算法】合并两个有序链表(easy)——递归算法
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
54 5
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
41 4
|
3月前
|
Python
【Python】正则表达式判断是否存在连续N个字母
文章提供了一个Python函数five_continue,使用正则表达式来判断字符串中是否存在连续5个或更多字母的情况,并返回存在此类序列的布尔值。
53 2