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

LeetCode518:零钱兑换

题目链接:518. 零钱兑换 II - 力扣(LeetCode)

代码如下

class Solution {
public:int change(int amount, vector<int>& coins) {vector<unsigned int> dp(amount + 10, 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];}
};

首先来讲一下这个代码的一个需要注意的语法 vector<unsigned int> dp(amount + 10, 0);这个至少对于我来说我是第一次见的,这个作用就是unsigned int, 也就是无符号整型,也就是说范围是在1~2^31-1,  而平常的int其实是signed int的缩写, 所以来说, 这个范围是-2^31-1 ~ 2^31-1这个范围.

题目讲解:首先我们要知道这个题目要求的是有几种方法可以凑成这个amount,也就是我把amount当成一个背包容量,既然说钞票无限使用,我们肯定想到的是用完全背包。这个题目递推公式和之前的(leetcode494:目标和题目)一样的方法推到出来的,然后该初始化了,dp[0] = 1;这个是为了能够递推后面的值,要是初始化为0的话,那么后面的值是无法被覆盖的。

两个for循环颠倒的意义

第一个:先遍历物品再遍历背包(组合数)

for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包

这个求出来的是凑出这个amount的组合数,为什么这么说的,因为先遍历物品,肯定是先遍历1,然后遍历2,所以背包里面的组合就是有顺序的,{1,2}

第二个:先遍历背包再遍历物品(排列数)

for (int j = 0; j <= amount; j++) { // 遍历背包for (int i = 0; i < coins.size(); i++) { // 遍历物品

这个求出来的是凑出这个amount的排列数,因为是把背包定下来的,背包里面放入物品1,2,3.....,所以来说背包里面的物品是没有先后顺序的,所组成的数就是{1,2},{2,1},这两个都能讲的通.


http://www.mrgr.cn/news/47008.html

相关文章:

  • LVGL移植高通点阵字库GT30L24A3W
  • LangChain学习笔记2 Prompt 模板
  • 数据结构之哈希表
  • 【开发日记】Docker修改国内镜像源
  • 【动手学电机驱动】STM32-MBD(5)Simulink 模型开发之 PWM 输出
  • WPF基础(1.1):ComboBox的使用
  • 【华为】默认路由配置
  • React(一) 认识React、熟悉类组件、JSX书写规范、嵌入变量表达式、绑定属性
  • ChinaER:重塑跨境互联新体验
  • 【Python脚本】getopt参数解析笔记
  • 【数据结构】顺序表
  • 推理实现new操作符
  • AI绘画Stable Diffusion XL优化终极指南!
  • CSS 命名规范及 BEM 在前端开发中的实践
  • 《网络基础之 HTML 与 CSS 基础 —— 网页的基本结构解析》
  • 力扣1~10题
  • acme.sh在nginx环境配置,ssl证书测试
  • HCIE的含金量都是被吹出来的?
  • 洗衣店订单管理:Spring Boot技术革新
  • [实用工具]Docker安装nextcloud实现私有云服务和onlyoffice
  • 【工具】前端js数字金额转中文大写金额
  • JAVA中的线程控制
  • 画质修复怎么弄?这4个恢复照片清晰度的修复工具快收藏
  • vue3学习记录-watch
  • 智慧水利(数字孪生流域)建设方案
  • 从不同的细节察觉人的性格