代码随想录算法训练营Day45 | 70. 爬楼梯 (进阶) 322. 零钱兑换 279.完全平方数

news/2024/7/21 15:46:51/文章来源:https://blog.csdn.net/qq_24817679/article/details/139102560

代码随想录算法训练营Day45 | 70. 爬楼梯 (进阶) 322. 零钱兑换 279.完全平方数

LeetCode 70. 爬楼梯(进阶)

题目链接:LeetCode 70. 爬楼梯(进阶)

思路:

#include <iostream>
#include <vector>
using namespace std;int main(){int m, n;while (cin>>n>>m){vector<int> dp(n+1);dp[0] = 1;for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(i-j>=0) dp[i] += dp[i-j];}}cout << dp[n];}return 0;}

注意 :

  1. n为背包容量,m为物品

LeetCode 322. 零钱兑换

题目链接:LeetCode 322. 零钱兑换

思路:

可重复,完全背包

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

注意 :

  1. 先循环coin 再循环item

LeetCode 279.完全平方数

题目链接:LeetCode 279.完全平方数

思路:

完全背包

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1, INT_MAX);dp[0] = 0;for(int i=1; i<=n; i++){for(int j=1; j*j<=i; j++){dp[i] = min(dp[i], dp[i-j*j] + 1);}}return dp[n];}
};

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

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

相关文章

3W 1.5KVDC 隔离 宽范围输入,双隔离双输出 DC/DC 电源模块——TPD-3W系列

TPD-3W系列产品是专门针对线路板上分布式电源系统中需要产生一组与输入电源隔离的双隔离双电源的应用场合而设计。该产品适用于&#xff1a;1&#xff09;输入电源的电压变化范围≤2&#xff1a;1 &#xff1b;2&#xff09;输入输出之间要求隔离≤1500VDC&#xff1b;3&#x…

unity回到低版本报错解决

用高版本2022打开过后的再回到2020就报了一个错。 报错如下&#xff1a; Library\PackageCache\com.unity.ai.navigation1.1.5\Runtime\NavMeshSurface.cs 看了一下是Library&#xff0c;然后我删除了整个Library文件夹&#xff0c;重启启动生成Library&#xff0c;然后还是…

Linux 查找命令的操作,学完效率瞬间翻倍?

可以很肯定地说&#xff0c;find 命令是 Linux 运维必须熟知的操作之一。 让我们看一道题&#xff1a; 如果你的 Linux 服务器上有一个名为 .logs 的目录&#xff0c;如何删除该目录下最后一次访问时间超过一年的日志文件呢&#xff1f; 这种情况很常见&#xff0c;但令人惊讶…

Oracle-修改用户名

1、项目背景 需要将导入一份最新的用户数据在tbl用户上&#xff0c;但需要将原来的tbl用户数据保留并能实现两个用户的比对。 2、解决思路 思路一&#xff1a;1&#xff09;新建用户tbl_feng,导入数据&#xff1b;2&#xff09;将两个用户换名称 3&#xff09;比对 思路二&…

关于解决Qt在安装的时候没有勾选sources组件的方法

关于解决Qt在安装的时候没有勾选sources组件的方法 一、引言 在安装数据库连接到qt的时候发现没有sources文件夹&#xff0c;原来是安装的时候没有勾选sources组件&#xff0c;发现问题后找到了维护qt组件的安装方式&#xff0c;特此记下来 二、分析原因 首先在安装的时候就…

Java并发面试题,多线程通关秘籍

【知识点记录】- 不能不知道的知识点 &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 博客首页 怒放吧德德 To记录领地 &#x1f31d;分享学习心得&#xf…

上海冠珠旗舰总店盛装开业暨冠珠瓷砖中国美学设计巡回圆满举办

上海&#xff0c;这座融合了东西方文化的国际化大都市&#xff0c;不仅是中国的时尚中心&#xff0c;也是全球潮流的汇聚地。在这里&#xff0c;古典与现代交织&#xff0c;传统与前卫并存&#xff0c;为传统色彩与现代设计的融合提供了得天独厚的条件。 5月25日&#xff0c;上…

拉普拉斯IPO:新能源产业快速发展,为低碳转型注入强劲动力

近年来&#xff0c;我国新能源产业快速发展&#xff0c;为全球绿色低碳转型注入强劲动力。国际人士认为&#xff0c;中国新能源产业快速发展&#xff0c;得益于超大规模市场优势、完整的工业体系和丰富的人力资源&#xff0c;得益于企业对研发创新的巨大投入&#xff0c;我国市…

linux线程,线程控制与线程相关概念

线程概念 线程这个词或多或少大家都听过&#xff0c;今天我们正式的来谈一下线程&#xff1b; 在我一开始的概念中线程就是进程的一部分&#xff0c;一个进程中有很多个线程&#xff0c;这个想法基本是正确的&#xff0c;但细节部分呢我们需要细细讲解一下&#xff1b; 什么…

C++ Primer 第五版 第十三章 拷贝控制

当定义一个类时&#xff0c;我们显式地或隐式地指定在此类型的对象拷贝、移动、赋值和销毁时做什么。一个类通过定义五种特殊的成员函数来控制这些操作&#xff0c;包括&#xff1a;拷贝构造函数&#xff08;copy constructor&#xff09;、拷贝赋值运算符&#xff08;copy-ass…

9、C#【进阶】特性

特性 文章目录 1、特性概念2、自定义特性 Attribute3、特性的使用4、限制自定义特性的使用范围5、系统自带特性1、过时特性2、调用者信息特性3、条件编译特性4、外部dll包函数特性 1、特性概念 特性是一种允许我们向程序的程序集添加元数据的语言结构 它是用于保存程序机构信息…

全网首发!精选32个最新计算机毕设实战项目(附源码),拿走就用!

Hi 大家好&#xff0c;马上毕业季又要开始了&#xff0c;陆陆续续又要准备毕业设计了&#xff0c;有些学生轻而易举就搞定了&#xff0c;有些学生压根没有思路怎么做&#xff0c;可能是因为技术问题&#xff0c;也可能是因为经验问题。 计算机毕业相关的设计最近几年类型比较多…

Docker 开启 SSL 验证

最近看 OJ 项目的远程开发阶段&#xff0c;然后踩坑踩了 2 天&#x1f602; Docker 版本&#xff1a;在 CentOS 安装 sudo yum install docker-ce-20.10.9 docker-ce-cli-20.10.9 containerd.io Client: Docker Engine - CommunityVersion: 20.10.9API version: …

如何远程访问Redis?

远程访问Redis是一种常见的需求&#xff0c;特别是在分布式系统或跨地域网络中。通过远程访问&#xff0c;我们可以轻松地对远程的Redis数据库进行操作和管理。 天联保障数据安全 对于远程访问Redis的安全性问题&#xff0c;我们可以借助天联来保障数据的安全。天联是一种基于…

Pytorch创建张量

文章目录 1.torch.from_numpy()2. torch.zeros()3. torch.ones()4. torch.arange()5. torch.linspace()6. torch.logspace()7. torch.eye()8. torch.empty()9. torch.full()10. torch.complex()10. torch.rand()10. torch.randint()11. torch.randn12. torch.normal()13. torch…

概率分布函数与误差函数的关系

正态函数&#xff08;高斯分布&#xff09; 对其求[b,x]区间的积分 标准误差函数 以下两个方程相等&#xff08;a,b取值任意&#xff09; 两个函数重合 可知正态函数 f(t) 在[b,x]的区间上积分等于 引用desmos计算器&#xff1a;Desmos | Lets learn together.

9.4 Go语言入门(运算符)

Go语言入门&#xff08;运算符&#xff09; 目录三、运算符1. 算术运算符2. 关系运算符3. 逻辑运算符4. 位运算符5. 赋值运算符6. 其他运算符7. 运算符优先级 目录 Go 语言&#xff08;Golang&#xff09;是一种静态类型、编译型语言&#xff0c;由 Google 开发&#xff0c;专注…

他用AI,抄袭了我的AI作品

《大话西游》里面有一句经典台词&#xff1a;每个人都有一个妈&#xff0c;但是“你妈就一定是你妈吗&#xff1f;” 用AI创作的艺术作品&#xff0c;也走进类似的困境&#xff1a;如何证明你用AI生成的作品&#xff0c;就是你的作品&#xff1f; 近日&#xff0c;腾讯科技独…

编程-辅助工具-Git下载

文章目录 1、前言2、Git官网地址3、迅雷下载 1、前言 采用Git能下载github上的代码&#xff0c;其下载是采用官网下载的&#xff0c;但是下载速度比较慢&#xff0c;网上也推荐了镜像的方式&#xff0c;但是有些链接失效了&#xff0c;突然有一天想起用迅雷是不是合适&#xf…

【Sql Server】随机查询一条表记录,并重重温回顾下存储过程的封装和使用

大家好&#xff0c;我是全栈小5&#xff0c;欢迎来到《小5讲堂》。 这是《Sql Server》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 目录 前言随机查询语…