当前位置: 首页 > article >正文

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(39)玲珑棋局摆硬币 - 零钱兑换(完全背包)

《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(39)玲珑棋局摆硬币 - 零钱兑换(完全背包)

哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的玲珑棋局,棋局中摆放着各种面值的硬币。棋局的入口处有一块巨大的石碑,上面刻着一行文字:“欲破此局,需以玲珑棋局之力,摆硬币,完全背包显真身。”

哪吒定睛一看,石碑上还有一行小字:“给定硬币面值[1, 2, 5]和目标金额11,最少需要3枚硬币(5 + 5 + 1)。”哪吒心中一动,他知道这是一道关于零钱兑换的难题,需要通过完全背包的动态规划方法,找到最少的硬币数量。

暴力解法:玲珑棋局的初次尝试

哪吒心想:“要找到最少的硬币数量,我可以逐个硬币尝试。”他催动玲珑棋局之力,通过递归的方式,枚举所有可能的硬币组合,试图找到最少的硬币数。

int coinChange(vector<int>& coins, int amount) {
   
    if (amount == 0) return 0;
    int minCoins = INT_MAX;
    for (int coin : coins) {
   
        if (coin <= amount) {
   
            int result = coinChange(coins, amount - coin);
            if (result != -1) {
   
                minCoins = min(minCoins, result + 1);
            }
        }
    }
    return minCoins == INT_MAX ? -1 : minCoins;
}

哪吒成功地找到了最少的硬币数量,但玲珑棋局的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当目标金额很大时,灵力消耗巨大。

C++语法点

在C++中,完全背包问题通常使用动态规划来解决。以下是一些重要特性:

  • 动态规划数组

    • 使用vector<int>来表示动态规划数组。
    • 常用操作:
      • dp[i]:表示金额为i时的最少硬币数。
      • 初始化动态规划数组:vector<int> dp(amount + 1, INT_MAX)
  • 循环结构

    • 外层循环遍历硬币面值。
    • 内层循环遍历目标金额。

高阶优化:完全背包的智慧

哪吒元神中突然浮现金色铭文——「玲珑棋局摆硬币,完全背包显真身」。他意识到,可以通过完全背包的动态规划方法,优化零钱兑换问题的解决过程。

哪吒决定使用动态规划,创建一个数组dp,其中dp[i]表示金额为i时的最少硬币数。通过初始化dp[0] = 0,然后遍历每个硬币面值,更新dp数组。通过这种方式,他成功地找到了最少的硬币数量,而且灵力消耗大幅减少。

int coinChange(vector<int>& coins, int amount) {
   
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;
    for (int coin : coins) {
   
        for 

http://www.kler.cn/a/587563.html

相关文章:

  • python列表基础知识
  • 3.4 Spring Boot整合Elasticsearch:全文检索与聚合分析
  • 信奥赛CSP-J复赛集训(模拟算法专题)(16):P6386 [COCI 2007/2008 #4] VAUVAU
  • Linux下对2TB磁盘的分区、格式化、挂截目录介绍
  • 用Python和Pygame实现打砖块游戏
  • HTML编辑MP4保存名称
  • DBeaver部分操作指南(数据库连接,构造ERD图,格式化SQL)
  • Hive函数大全:从核心内置函数到自定义UDF实战指南(附详细案例与总结)
  • 无电池也能通信!中国移动5G-A芯片重塑物联网未来
  • P2512糖果传递 P4447分组 P1080国王游戏 P4053建筑抢修
  • Python 字节码深度历险:dis 模块揭秘与性能优化实战
  • 深入探讨RAID 5的性能与容错能力:实验与分析(磁盘阵列)
  • Vue 中的 MVVM、MVC 和 MVP 模式深度解析
  • Java数据结构第二十三期:Map与Set的高效应用之道(二)
  • 深度迁移学习实战指南:从理论到产业级应用
  • 安装 MongoDB 的步骤(Windows / macOS / Linux)
  • Excel表一键查询工具
  • 简要分析NETLINK_USER参数
  • springboot系列十五:SpringBoot整合MyBatis, MyBatis-Plus
  • 【数据结构】数据结构,算法 概念