Leetcode:518. 零钱兑换 II(C++)
admin
2024-05-24 02:00:07
0

目录

518. 零钱兑换 II

问题描述:

实现代码与解析:

动态规划(完全背包):

原理思路:

377. 组合总和 Ⅳ

问题描述:

实现代码与解析:

动态规划(完全背包):

原理思路:


518. 零钱兑换 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

实现代码与解析:

动态规划(完全背包):

class Solution {
public:int change(int amount, vector& coins) {vector dp(amount + 1, 0);dp[0] = 1;for(int i = 0; i < coins.size(); i++){for(int j = coins[i]; j <= amount; j++){dp[j] += dp[j - coins[i]];}}return dp[amount];}
};

原理思路:

        和Leetcode:494. 目标和(C++)_Cosmoshhhyyy的博客-CSDN博客很像,只不过一个是一个数只能用一次,而本题可以用多次,也就是完全背包求组合数的问题,完全背包的代码可以看看

动态规划:0-1背包、完全背包问题 | 详细原理解释 | 代码及优化(C++)_Cosmoshhhyyy的博客-CSDN博客_c++代码优化工具        两者结合一下就很好写出了,不再解释了,比较简单。

377. 组合总和 Ⅳ

问题描述:

        给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。

示例 2:

输入:nums = [9], target = 3
输出:0

实现代码与解析:

动态规划(完全背包):

class Solution {
public:int combinationSum4(vector& nums, int target) {vector dp(target + 1, 0);dp[0] = 1;for(int j = 0; j <= target; j++){for(int i = 0; i < nums.size(); i++){if(j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]){dp[j] += dp[j - nums[i]];}             }}       return dp[target];}
};

原理思路:

        此题与上题相似,放在一次主要是注意这两题的差别,此题强调的是顺序,不同顺序也是一个结果,而上一题顺序无所谓,只算一总结果。

        先说结论吧,先遍历物品的话,就是上一题不用管顺序,先遍历背包的话,就是这题需要在意顺序。

        注意这个 if 的判断阿,因为我们先遍历背包了,int j = nums[i] 的逻辑就只能放在这里了。

if(j >= nums[i])
{dp[j] += dp[j - nums[i]];
}      

        因为有一组测试数据相加超过int范围,所以就多加了一个dp[j] < INT_MAX - dp[j - nums[i]]的判断,其余不变。

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作: 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统(六):学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤: 在Student.cpp的...
JAVA多线程知识整理 Java多线程基础 线程的创建和启动 继承Thread类来创建并启动 自定义Thread类的子类&#...
【洛谷 P1090】[NOIP... [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G ...
国民技术LPUART介绍 低功耗通用异步接收器(LPUART) 简介 低功耗通用异步收发器...
城乡供水一体化平台-助力乡村振... 城乡供水一体化管理系统建设方案 城乡供水一体化管理系统是运用云计算、大数据等信息化手段࿰...
程序的循环结构和random库...   第三个参数就是步长     引入文件时记得指明字符格式,否则读入不了 ...
中国版ChatGPT在哪些方面... 目录 一、中国巨大的市场需求 二、中国企业加速创新 三、中国的人工智能发展 四、企业愿景的推进 五、...
报名开启 | 共赴一场 Flu... 2023 年 1 月 25 日,Flutter Forward 大会在肯尼亚首都内罗毕...
汇编00-MASM 和 Vis... Qt源码解析 索引 汇编逆向--- MASM 和 Visual Studio入门 前提知识ÿ...
【简陋Web应用3】实现人脸比... 文章目录🍉 前情提要🌷 效果演示🥝 实现过程1. u...
前缀和与对数器与二分法 1. 前缀和 假设有一个数组,我们想大量频繁的去访问L到R这个区间的和,...
windows安装JDK步骤 一、 下载JDK安装包 下载地址:https://www.oracle.com/jav...
分治法实现合并排序(归并排序)... 🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨...
在linux上安装配置node... 目录前言1,关于nodejs2,配置环境变量3,总结 前言...
Linux学习之端口、网络协议... 端口:设备与外界通讯交流的出口 网络协议:   网络协议是指计算机通信网...
Linux内核进程管理并发同步... 并发同步并发 是指在某一时间段内能够处理多个任务的能力,而 并行 是指同一时间能够处理...
opencv学习-HOG LO... 目录1. HOG(Histogram of Oriented Gradients,方向梯度直方图)1...
EEG微状态的功能意义 导读大脑的瞬时全局功能状态反映在其电场结构上。聚类分析方法一致地提取了四种头表面脑电场结构ÿ...
【Unity 手写PBR】Bu... 写在前面 前期积累: GAMES101作业7提高-实现微表面模型你需要了解的知识 【技...