IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> leetcode 322 零钱兑换 -> 正文阅读

[数据结构与算法]leetcode 322 零钱兑换

题目

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

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

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

示例

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

解析

这道题和之前的零钱兑换区别是,之前是问有多少种兑换方法,本题是问最少硬币个数,先用动规五部曲分析一波:
1.确定dp数组以及下标的含义
dp[j]:凑足总额为j所需钱币的最少个数为dp[j]
2.递推公式
凑足总额为j - coins[i]的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i],注意,这里是加一个硬币,数量是1 就可以了,即dp[j - coins[i]] + 1就是dp[j](考虑coins[i])
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
3.初始化
凑成总金额为0需要的最小硬币数量一定是0,所以dp[0] = 0
除此之外,因为要求最小值,那么比较的时候,要先把整个数组初始化为最大值才行
4.遍历顺序

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    dp[0] = 0 // dp数组表示凑成总金额为0需要的最小硬币数量一定是0
    for i := 1; i < amount+1; i++ {
        dp[i] = math.MaxInt32 //因为要求最小数量,所以全部初始化为最大值
    }
    for i := 1; i <= amount; i++ { //遍历背包,0 没啥用不需要遍历了
        for j := 0; j < len(coins); j++ { //遍历物品
            if i - coins[j] >= 0 { // 注意是谁和谁比较大小,是背包容量大于本次物品的价值
                dp[i] = min(dp[i], dp[i-coins[j]]+1)
            }
        }
    }
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a > b {
        return b
    }
    return a
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-12-25 11:33:24  更:2022-12-25 11:38:42 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年6日历 -2024/6/17 6:33:31-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码