力扣--动态规划完全背包/深度优先08.11.零币

如果暴力的深度优先:
 

class Solution {
    // 定义硬币的面值数组
    int fangx[4] = {25, 10, 5, 1};
    // 计数变量,用于记录配合得到 n 的方法数
    long long count = 0;

    // 定义深度优先搜索函数
    // now: 当前总值
    // n: 目标总值
    // notbig: 上一次选择的硬币面值索引
    int dfs(int now, int n, int notbig) {
        // 当前总值等于目标总值时,方法数加一
        if (now == n) {
            count += 1;
            count %= 1000000007; // 防止计数过大,取模
            return 0;
        }
        // 当前总值大于目标总值时,返回
        if (now > n)
            return 0;
        // 遍历硬币面值数组,从上一次选择的硬币面值索引开始,防止重复计算
        for (int i = notbig; i < 4; i++) {
            // 递归调用深度优先搜索,更新当前总值为当前总值加上当前面值硬币的值
            dfs(now + fangx[i], n, i);
        }
        return 0;
    }

public:
    // 定义计算配合得到 n 的方法数的函数
    int waysToChange(int n) {
        // 调用深度优先搜索函数
        dfs(0, n, 0);
        // 返回计数结果
        return count;
    }
};

但是很不幸,示例(28/30)无法完全通过,还是有点超时了。


那么我们考虑,不限各类硬币数,而且可以看作:面值25的硬币重量是25,价值也是25,这可以视为动态规划里面的完全背包问题,那么就简单了。

class Solution {
    // 定义硬币的面值数组
    int fangx[4] = {1, 5, 10, 25};

public:
    // 计算配合得到 n 的方法数的函数
    int waysToChange(int n) {
        // 定义动态规划数组,长度为 n+1,初始化为0
        vector<int> dp(n + 1, 0);
        // 初始情况:当目标总值为0时,有一种方法,即不选取任何硬币
        dp[0] = 1;

        // 遍历硬币面值数组
        for (int i = 0; i < 4; i++) {
            // 遍历从当前硬币面值到目标总值的所有可能情况
            for (int j = fangx[i]; j <= n; j++) {
                // 更新动态规划数组中第 j 个元素的值
                // 第 j 个元素的值等于第 j 个元素原有的值加上第 j-fangx[i] 个元素的值
                // 即当前面值的硬币可以选择不同数量,对应不同情况下的配合方法数
                dp[j] += dp[j - fangx[i]];
                // 由于涉及大数运算,取模以避免溢出
                dp[j] %= 1000000007;
            }
        }
        // 返回配合得到目标总值 n 的方法数
        return dp[n];
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/527903.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PCB学习记录-----入门基础知识

一、搭建环境 1.下载嘉立创EDA 软件下载 - 嘉立创EDA (lceda.cn) 选专业版 在线编辑&#xff1a;嘉立创EDA(专业版) - V2.1.45 (lceda.cn) 官方教程&#xff1a;立创EDA专业版-使用教程 (lceda.cn) 2.新建工程 文件-新建-项目&#xff0c;右键Board1可以重命名&#xff…

Debian 12.0安装NVM管理器

cd到一个自己创建的目录 要在Debian 12.0上安装 Node Version Manager&#xff08;NVM&#xff09;来管理 Node.js 版本&#xff0c;您可以按照以下步骤进行操作&#xff1a; 首先&#xff0c;您需要使用 cURL 下载 NVM 安装脚本。在终端中运行以下命令&#xff1a; curl -o…

读博做FPGA上的AI加速能不能搞啊?

从企业的角度来看&#xff0c;选择在FPGA上进行AI加速仍然有其一定的优势和适用场景&#xff0c;但也有一些挑战需要考虑。我这里有一套嵌入式入门教程&#xff0c;不仅包含了详细的视频讲解&#xff0c;项目实战。如果你渴望学习嵌入式&#xff0c;不妨点个关注&#xff0c;给…

使用Datax自定义采集组件Reader/Writer实现国产数据库支持以及_Datax数据清洗/过滤规则功能自定义---大数据之DataX工作笔记007

我们基于datax来做的自己的数据采集系统,现在基本的数据采集已经实现了,也就是调用datax的数据采集能力,实现在已支持的数据库之间同步数据.我们是基于datax-web实现的,里面都有开源的代码了,可以分析以后拿过来用,这个过程并不复杂,而且,结合xxljob的web那个开源项目,也可以让…

S19文件解析

目录 一、概述 二、S19文件解析 三、举例 一、概述&#xff1a; Motorola S-record是一种文件格式&#xff0c;由摩托罗拉在20世纪70年代中期为Motorola 6800处理器创建&#xff0c;以ASCII文本形式传达二进制信息的十六进制值&#xff0c;其文件格式也可能为SRECORD&#xf…

如何使用宝塔面板搭建MySQL数据库并实现无公网IP远程访问

文章目录 前言1.Mysql服务安装2.创建数据库3.安装cpolar3.2 创建HTTP隧道 4.远程连接5.固定TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 前言 宝塔面板的简易操作性,使得运维难度降低,简化了Linux命令行进行繁琐的配置,下面简单几步,通过宝塔面板cp…

Macos 部署自己的privateGpt(2024-0404)

Private Chatgpt 安装指引 https://docs.privategpt.dev/installation/getting-started/installation#base-requirements-to-run-privategpt 下载源码 git clone https://github.com/imartinez/privateGPT cd privateGPT安装软件 安装&#xff1a; Homebrew /bin/bash -c…

《C语言深度解剖》(3):探索函数递归、传值、传址调用的奥秘

&#x1f921;博客主页&#xff1a;醉竺 &#x1f970;本文专栏&#xff1a;《C语言深度解剖》 &#x1f63b;欢迎关注&#xff1a;感谢大家的点赞评论关注&#xff0c;祝您学有所成&#xff01; ✨✨&#x1f49c;&#x1f49b;想要学习更多数据结构与算法点击专栏链接查看&am…

Linux锁的使用

一、临界资源与临界区 多线程会共享例如全局变量等资源&#xff0c;我们把会被多个执行流访问的资源称为临界资源&#xff0c;我们是通过代码访问临界资源的&#xff0c;而我们访问临界资源的那部分代码称为临界区。 实现一个抢票系统 只有一个线程抢票时 #include <ios…

【二分查找】Leetcode 寻找峰值

题目解析 162. 寻找峰值 题目中有一个很重要的提示&#xff1a;对所有有效的i都存在nums[i] ! nums[i1],因此这道题不需要考虑nums[mid] 和 nums[mid1]之间的相等与否的关系 算法讲解 1. 暴力枚举 我们按照顺序判断每个数字是否是当前的峰值&#xff0c;如果是直接返回&#…

【WEEK7】 【DAY1】索引【中文版】

2024.4.8 Monday 目录 7.索引7.1.内涵7.2.索引的作用7.3.索引的分类7.3.1.主键索引&#xff08;PRIMARY KEY&#xff09;7.3.1.1.主键 : 某一个属性组能唯一标识一条记录7.3.1.2.特点 : 7.3.2.唯一索引&#xff08;UNIQUE KEY&#xff09;7.3.2.1.作用 : 避免同一个表中某数据…

第一部分 Vue讲解(代码版)

1.第一个vue实例 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice-w…

获得乙级风力发电设计资质需要哪些注册工程师资格?

要获得乙级风力发电设计资质&#xff0c;通常需要以下注册工程师资格&#xff1a; 注册电气&#xff08;发输电&#xff09;工程师&#xff1a;他们负责风力发电项目的电气系统设计、优化、设备选型和配置&#xff0c;确保电力供应的安全性和可靠性。他们的专业知识对于保证风…

SpringBoot的旅游管理系统+论文+ppt+免费远程调试

项目介绍: 基于SpringBoot旅游网站 旅游管理系统 本旅游管理系统采用的数据库是Mysql&#xff0c;使用SpringBoot框架开发。在设计过程中&#xff0c;充分保证了系统代码的良好可读性、实用性、易扩展性、通用性、便于后期维护、操作方便以及页面简洁等特点。 &#xff08;1&…

吴恩达深度学习笔记:深层神经网络(Deep Neural Networks)4.5-4.8

目录 第一门课&#xff1a;神经网络和深度学习 (Neural Networks and Deep Learning)第四周&#xff1a;深层神经网络(Deep Neural Networks)4.5 为什么使用深层表示&#xff1f;&#xff08;Why deep representations?&#xff09; 第一门课&#xff1a;神经网络和深度学习 (…

5.网络编程-socker(golang版)

目录 一、什么是socket&#xff1f; 二、Golang中使用TCP TCP服务端 TCP客户端​​​​​​​ 三、TCP黏包&#xff0c;拆包 1.什么是粘包&#xff0c;拆包&#xff1f; 2.为什么UDP没有粘包&#xff0c;拆包&#xff1f; 3.粘包拆包发生场景 4.TCP黏包 黏包服务端 …

官宣定档“2024上海国际半导体产业展会”定于11月份在沪召开

2024上海国际半导体产业展览会 2024 Shanghai Semiconductor Expo 时间:2024年11月18-20日 地点:上海新国际博览中心 前言 近年来&#xff0c;上海半导体产业呈现出快速发展的态势。一方面&#xff0c;得益于国家政策的大力支持&#xff0c;上海半导体产业得到了迅猛的发展。…

计算机组成结构2

概念 存储系统 解决成本-速度-容量之前的矛盾问题 寄存器–cache–内存–硬盘–外存储 局部性原理 时间局部&#xff1a;相邻的时间访问同一个数据空间局部&#xff1a;相邻的空间地址会被连续访问 cache cpu与主存之间&#xff0c;命中cache后就不需要访问主存&#xff0c;…

景联文科技:为AI大模型提供高质海量训练数据

在全球AI浪潮的推动下&#xff0c;大量训练数据已成为AI算法模型发展和演进中的关键一环。 艾瑞咨询数据显示&#xff0c;包括数据采集、数据处理&#xff08;标注&#xff09;、数据存储、数据挖掘等模块在内的AI基础数据服务市场&#xff0c;将在未来数年内持续增长。 预计到…

跟着GPT学设计模式之适配器模式

题图来自APOD 你好&#xff0c;这里是codetrend专栏“跟着GPT学设计模式”。 说明 适配器模式&#xff08;Adapter Pattern&#xff09;是一种结构型设计模式&#xff0c;用于将一个类的接口转换为客户端所期望的另一个接口。适配器模式允许不兼容的接口协同工作&#xff0c…