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

算法打卡 Day41(动态规划)-理论基础 + 斐波那契数 + 爬楼梯 + 使用最小花费爬楼梯

文章目录

  • 理论基础
  • Leetcode 509-斐波那契数
    • 题目描述
    • 解题思路
  • Leetcode 70-爬楼梯
    • 题目描述
    • 解题思路
  • Leetcode 746-用最小花费爬楼梯
    • 题目描述
    • 解题思路

理论基础

动态规划,简称 DP,其中的每一个状态一定是由上一个状态推导出来的,而贪心算法没有状态推导,只是从局部直接选最优。

动态规划的五步:

  1. 确定 dp 数组以及下标的含义
  2. 确定递推公式
  3. dp 数组如何初始化
  4. 确定遍历顺序
  5. 举例推导 dp 数组

Leetcode 509-斐波那契数

题目描述

https://leetcode.cn/problems/fibonacci-number/description/

在这里插入图片描述

解题思路

class Solution {
public:int fib(int n) {vector<int> dp(n+1);dp[0] = 0;if (n > 0) dp[1] = 1;for (int i = 2; i <=n; i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

注意考虑 n=0 的情况,如果不加限制条件直接写 dp[1] = 1 会报错因为数组越界

Leetcode 70-爬楼梯

题目描述

https://leetcode.cn/problems/climbing-stairs/description/

在这里插入图片描述

解题思路

class Solution {
public:int climbStairs(int n) {vector<int> dp(n);dp[0] = 1;if (n>1) dp[1] = 2;for (int i = 2; i <n;i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n-1];}
};

Leetcode 746-用最小花费爬楼梯

题目描述

https://leetcode.cn/problems/min-cost-climbing-stairs/description/

在这里插入图片描述

解题思路

本题的解题思路继承爬楼梯,在此基础上还需要考虑爬楼梯的费用

class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> dp(cost.size());//dp保存的是到当前楼梯的最低花费int n = cost.size();dp[0] = 0;dp[1] = 0;for (int i =2; i < n;i++){dp[i] = min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);}int minExpense = min(dp[n-1]+cost[n-1],dp[n-2]+cost[n-2]);return minExpense;}
};

相关文章:

算法打卡 Day41(动态规划)-理论基础 + 斐波那契数 + 爬楼梯 + 使用最小花费爬楼梯

文章目录 理论基础Leetcode 509-斐波那契数题目描述解题思路 Leetcode 70-爬楼梯题目描述解题思路 Leetcode 746-用最小花费爬楼梯题目描述解题思路 理论基础 动态规划&#xff0c;简称 DP&#xff0c;其中的每一个状态一定是由上一个状态推导出来的&#xff0c;而贪心算法没有…...

鸿蒙环境服务端签名直传文件到OSS

本文介绍如何在鸿蒙环境下将文件上传到OSS。 背景信息 鸿蒙环境是当下比较流行的操作环境&#xff0c;与服务端签名直传的原理类似&#xff0c;鸿蒙环境上传文件到OSS是利用OSS提供的PutObject接口来实现文件上传到OSS。关于PutObject的详细介绍&#xff0c;请参见PutObject。…...

计算机毕业设计Python+Flask微博情感分析 微博舆情预测 微博爬虫 微博大数据 舆情分析系统 大数据毕业设计 NLP文本分类 机器学习 深度学习 AI

首先安装需要的python库&#xff0c; 安装完之后利用navicat导入数据库文件bili100.sql到mysql中&#xff0c; 再在pycharm编译器中连接mysql数据库&#xff0c;并在设置文件中将密码修改成你的数据库密码。最后运行app.py&#xff0c;打开链接&#xff0c;即可运行。 B站爬虫数…...

solidwork剪裁实体

之前是这样&#xff1a; 效果如下&#xff1a;...

Junit与Spring Test简单使用

Junit与Spring Test简单使用 Junit5简介Junit5 注解Junit5与Spring结合 差异概览MockingMockBeanSpyBeanDemo 注意事项 又要写测试代码了&#xff0c;总结记录一下。 Junit5简介 与单一模块设计的Junit4不同,Junit5引入了模块化架构,由三个主要子项目组成&#xff1a; JUnit Pl…...

Vxe UI vue vxe-table 实现自适应列宽,根据内容自适应列的宽度

Vxe UI vue vxe-table 实现自适应列宽&#xff0c;根据内容自适应列的宽度 之前老版本是通过计算字符数量&#xff0c;然后给动态给每一列设置宽度&#xff0c;不仅麻烦&#xff0c;还不好复用。 看了 API 发现 v4.7 和 v3.9 版本已经直接就能支持了&#xff0c;只需加上 widt…...

document.visibilityState 监听浏览器最小化

1.document.hidden&#xff1a; 表示页面是否隐藏的布尔值。页面隐藏包括 页面在后台标签页中 或者 浏览器最小化 &#xff08;注意&#xff0c;页面被其他软件遮盖并不算隐藏&#xff0c;比如打开的 sublime 遮住了浏览器&#xff09;。 2.document.visibilityState&#xff…...

前端框架对比和选择

​ 大家好&#xff0c;我是程序员小羊&#xff01; 前言&#xff1a; 前端框架选择是前端开发中的关键决策&#xff0c;因为它影响项目的开发效率、维护成本和可扩展性。当前&#xff0c;最流行的前端框架主要包括 React、Vue 和 Angular。它们各有优劣&#xff0c;适用于不同…...

Linux 进程2

环境变量 再Linux操作系统中一切皆文件&#xff0c;这个环境变量自然也是一个文件&#xff0c;它的作用是辅助我们使用操作系统还可以辨识我们是什么用户(一般用户&#xff0c;root用户)。 env是读取完整环境变量的指令&#xff0c;里面记录了许多我登录操作系统所用的用户的信…...

WPF入门教学六 Grid布局进阶

在WPF&#xff08;Windows Presentation Foundation&#xff09;中&#xff0c;Grid布局是一种非常强大且灵活的布局控件&#xff0c;它允许你创建复杂的用户界面。以下是Grid布局的一些进阶技巧和教学&#xff1a; 一、基本概念回顾 Grid定义&#xff1a;Grid是一个用于布局…...

while循环及简单案例

//循环是流程控制中的一个重要分支 //流程控制 条件判断 循环 逻辑处理 //循环的目的和意义 //循环的目的是为了执行一块代码 //循环的意义是为了简化代码。增加代码的复用性 /* //例如输出0-100的数…...

电子看板实时监控数据可视化助力工厂精细化管理

在当今竞争激烈的制造业领域&#xff0c;工厂的精细化管理成为提高竞争力的关键。而电子看板实时监控数据可视化作为一种先进的管理工具&#xff0c;正为工厂的精细化管理带来巨大的助力。 一、工厂精细化管理的挑战 随着市场需求的不断变化和客户对产品质量要求的日益提高&am…...

邮储银行:面向金融行业的移动应用安全风险监测案例

本项目通过在移动应用中植入威胁情报探针并结合网络镜像流量方式,利用应用运行过程中设备、系统、应用、行为四个维度数据,将其与设备的关键因子关联生成唯一的移动设备指纹;对手机银行等应用资产进行资产台账梳理;结合服务端大数据分析平台的各种模型规则分析,实时监测移…...

ARMxy车辆数据采集Linux智能控制器

在当今科技日新月异的时代&#xff0c;高效智能的边缘计算设备在众多领域发挥着关键作用。我们的 ARM 边缘计算机&#xff0c;凭借其卓越的性能和广泛的适用性&#xff0c;成为车队管理智能化的核心力量。 一、强大硬件配置&#xff0c;完美适配车队管理需求 ARM 边缘计算机支…...

7.Java高级编程 多线程

Java高级编程 多线程 文章目录 Java高级编程 多线程一、进程与线程查看线程 二、线程创建方式三、线程状态四、线程常用方法五、线程安全 一、进程与线程 一个程序有一个进程 一个进程包含多个线程&#xff08;必须有一个主线程&#xff09; 并发&#xff1a; 在同一时刻&a…...

MT8370|MTK8370(Genio 510 )安卓核心板参数介绍

MTK Genio 510 (MT8370)安卓核心板是一款极为先进的高性能平台&#xff0c;专为满足边缘处理、先进多媒体功能及全面的连接需求而设计&#xff0c;适用于多种人工智能(AI)和物联网(IoT)应用场景。它具备多个高分辨率摄像头支持和可联网触摸屏显示&#xff0c;适用于使用多任务高…...

动物识别系统Python+卷积神经网络算法+TensorFlow+人工智能+图像识别+计算机毕业设计项目

一、介绍 动物识别系统。本项目以Python作为主要编程语言&#xff0c;并基于TensorFlow搭建ResNet50卷积神经网络算法模型&#xff0c;通过收集4种常见的动物图像数据集&#xff08;猫、狗、鸡、马&#xff09;然后进行模型训练&#xff0c;得到一个识别精度较高的模型文件&am…...

【STL】priority_queue 基础,应用与操作

c在C的标准模板库&#xff08;STL&#xff09;中&#xff0c;priority_queue 是一个基于堆的容器适配器&#xff0c;用于实现优先级队列。它本质上是一个最大堆&#xff08;Max-Heap&#xff09;&#xff0c;即每次取出元素时&#xff0c;始终取出优先级最高的元素。本文将详细…...

tasklist命令的应用实例

tasklist命令的应用实例 引言 在系统管理和故障排查过程中&#xff0c;了解当前正在运行的进程信息是至关重要的。Windows操作系统提供了一个强大的命令行工具——tasklist&#xff0c;它可以帮助用户查看当前系统中所有正在运行的进程及其相关信息。掌握这个命令的使用&…...

基于协同过滤算法+PHP的新闻推荐系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、SSM项目源码 系统展示 【2025最新】基于协同过滤算法PHPMySQL的新…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

es6+和css3新增的特性有哪些

一&#xff1a;ECMAScript 新特性&#xff08;ES6&#xff09; ES6 (2015) - 革命性更新 1&#xff0c;记住的方法&#xff0c;从一个方法里面用到了哪些技术 1&#xff0c;let /const块级作用域声明2&#xff0c;**默认参数**&#xff1a;函数参数可以设置默认值。3&#x…...

Monorepo架构: Nx Cloud 扩展能力与缓存加速

借助 Nx Cloud 实现项目协同与加速构建 1 &#xff09; 缓存工作原理分析 在了解了本地缓存和远程缓存之后&#xff0c;我们来探究缓存是如何工作的。以计算文件的哈希串为例&#xff0c;若后续运行任务时文件哈希串未变&#xff0c;系统会直接使用对应的输出和制品文件。 2 …...