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

java数据结构与算法刷题-----LeetCode70. 爬楼梯

java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846

很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只不过大家都叫它dp),达到空间换时间的效果。它仅仅只是一种优化思路,因此它目前的境地和线性代数一样----虚假的难。

  1. 想想线性代数,在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时,完全摸不着头脑,一上来就是行列式和矩阵,根本不知道这玩意是干嘛的。
  2. 线性代数从根本上是在空间上研究向量,抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。
  3. 反观国内的教材,直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候,只会觉得一知半解,觉得麻烦,完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候,发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材,什么狗东西(以上是自己学完线性代数后的吐槽,我们同学无一例外都这么觉得)。

而我想告诉你,动态规划和线性代数一样,我学完了才知道,它不过就是研究空间换时间,提前将固定的重复操作规划到dp数组中,而不用暴力求解,从而让效率极大提升。

  1. 但是网上教动态规划的兄弟们,你直接给一个动态方程是怎么回事?和线性代数,一上来就教行列式和矩阵一样,纯属恶心人。我差不多做了30多道动态规划题目,才理解,动态方程只是一个步骤而已,而这已经浪费我很长时间了,我每道题都一知半解不理解,过程及其痛苦。最后只能重新做。
  2. 动态规划,一定是优先考虑重复操作与dp数组之间的关系,搞清楚后,再提出动态方程。而你们前面步骤省略了不讲,一上来给个方程,不是纯属扯淡吗?
  3. 我推荐研究动态规划题目,按5个步骤,从上到下依次来分析
  1. DP数组及下标含义
  2. 递推公式
  3. dp数组初始化
  4. 数组遍历顺序(双重循环及以上时,才考虑)
  5. dp数组打印,分析思路是否正确(相当于做完题,检查一下)

在这里插入图片描述

拿到比较抽象的题,先列出前几项结果,尝试看出问题的本质(很多比较抽象的题,本质都很简单,抓住问题的本质,那么可以做到解决1道题,扩展到解决一类问题)
  1. n = 0时:结果为0
  2. n = 1时:结果为1
  3. n = 2时:结果为2
  4. n = 3时:结果为3
  5. n = 4时:结果为5

可见 这道题的规律0 1 2 3 5… 和斐波那契数列的0 1 1 2 3 5…非常像

什么是斐波那契数列?
  1. 斐波那契数列:第一个值是0,第二个值是1,剩下的元素是它前两个元素和,例如:0 1 1 2 3 5… , 可见除了最开始的两个固定为0和1外,其余每一个元素都是前两个元素的和。
  2. 也就是说,这玩意一看就是固定的一套值,如果每次都重新生成,就太暴力了。
  3. 动态规划的思想就是,将生成的过程,就生成一次,之后再用,直接从dp数组中拿。从而大大提升效率
解题思路
  1. 暴力求解的思想,就是定义3个或者2个变量,然后累加,以获得指定位置的斐波那契数。每次都需要从头开始累加
  2. 但是如果我们预先将其存储到dp数组,就可以直接通过dp[x], 获取dp数组中指定位置x的对应斐波那契数,而不用每次都从头计算。
  3. 但是这道题,从第4个元素开始,才符合斐波那契数列的规则,因此我们这道题,可以用斐波那契数列思想,但不能照搬
  4. 可见这道题,前3个为固定值 0 1 2 ,剩下的都是当前元素的前两项的和。
动态规划思考5步曲
  1. DP数组及下标含义

DP数组存储我们分析的类似斐波那契数列的数列,这个数列是一维线性的,所以只需一维数组存储。下标代表数列中的位置。dp[0] = 0,dp[1] = 1,dp[2]=2是头三个固定值(斐波那契数列头两个是固定值),dp[3]开始,每个元素是前两个数组元素的和。即可生成对应数列的dp数组。

  1. 递推公式

既然知道了DP数组就是存储的类似斐波那契数列的数列,那么递推公式,很显然就是当前元素=前两个元素的和。F(n) = F(n-1)+F(n-2)。 而且F(0) = 0,F(1)=1,F(2) = 2这是这个数列的特性,前三个值固定为0,1,2.

  1. dp数组初始化

在这里插入图片描述

  1. 数组遍历顺序(因为这个数列是一维的,只需要一重循环,无需考虑这个)
  2. 打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)

在这里插入图片描述

代码

在这里插入图片描述

class Solution {public int climbStairs(int n) {int length = n>=3?n:3;//避免n给的太小,例如n < 3时,下面的dp[2] = 2; 这条代码会下标越界//初始化DP数组,一维数组即可,头3个元素固定为0,1,2int dp[] = new int[length+1]; dp[0] = 0; dp[1] = 1;dp[2]=2;//其余元素为它的前两个元素的和for(int i = 3;i<=n ; i++){dp[i] = dp[i-1]+dp[i-2];}return dp[n];}
}

相关文章:

java数据结构与算法刷题-----LeetCode70. 爬楼梯

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 很多人觉得动态规划很难&#xff0c;但它就是固定套路而已。其实动态规划只…...

【Unity入门】UGUI之Slider(滑动条)

目录 一、什么是Slider&#xff1f;二、Slider属性与功能 一、什么是Slider&#xff1f; Slider控件允许用户可以通过鼠标来在预先确定的范围调节数值 我们可以在Hierarchy视图右键 -> UI ->Slider来创建滑动条 通过上图可以发现Unity内置的Slider主要有3部分&#x…...

MySQL中UNION和UNION ALL的区别有哪些?

在MySQL中如何想要对两个结果集进行合并操作&#xff0c;可以使用UNION和UNION ALL&#xff0c;如果只是想要去除掉重复的记录&#xff0c;属于UNION ALL 即可&#xff0c;但是如何想要除掉没有重复行数据&#xff0c;就要使用Union。本文详细向大家介绍MySQL中UNION和UNION AL…...

Android kotlin build.gradle.kts配置

1. 添加 maven 仓库 1. 1. settings配置 1. 1.1. settings.gradle repositories {maven {url https://maven.aliyun.com/repository/public/}mavenCentral() }1. 1.2. settings.gradle.kts repositories {maven {setUrl("https://maven.aliyun.com/repository/public/…...

css、js、vue常考部分面试题

css css盒子水平垂直居中方法 方法一&#xff1a;定位 .child{height: 100px;position: absolute;//父元素相对定位top:50%;left:50%;transform: translate(-50%,-50%); } 方法二&#xff1a;定位 .child{width: 100px;height: 100px;position: absolute;top:50%;left:50%…...

OpenAI ChatGPT-4开发笔记2024-03:Chat之Function Calling/Function/Tool/Tool_Choice

Updates on Function Calling were a major highlight at OpenAI DevDay. In another world,原来的function call都不再正常工作了&#xff0c;必须全部重写。 function和function call全部由tool和tool_choice取代。2023年11月之前关于function call的代码都准备翘翘。 干嘛…...

二叉搜索树与双向链表

解题思路一&#xff1a; /** public class TreeNode {int val 0;TreeNode left null;TreeNode right null;public TreeNode(int val) {this.val val;} } */ // 一定要用自己的理解真正弄出来才行&#xff0c;否则没有用&#xff01; // 再次提醒&#xff0c;计算机这种工科…...

uniapp中组件库的Checkbox 复选框 的丰富使用方法

目录 #平台差异说明 #基本使用 #自定义形状 #禁用checkbox #自定义形状 #自定义颜色 #横向排列形式 #横向两端排列形式 API #Checkbox Props #CheckboxGroup Props #CheckboxGroup Event 复选框组件一般用于需要多个选择的场景&#xff0c;该组件功能完整&#xff…...

Spring Cloud + Vue前后端分离-第10章 基于阿里云OSS的文件上传

源代码在GitHub - 629y/course: Spring Cloud Vue前后端分离-在线课程 Spring Cloud Vue前后端分离-第10章 基于阿里云OSS的文件上传 前面介绍的文件上传是基于本地文件服务器的文件上传&#xff0c;但是自己搭文件服务器会有很多运维的问题&#xff0c;比如磁盘满了要扩容…...

C++ 中的耗时计算函数

#include <time.h>int clock_gettime (clockid_t clock_id, struct timespec *tp) 获取当前 clock_id 的时钟值并存储在 tp 中。 其中 tp 是一个 timespec 结构体&#xff0c;在 time.h 头文件中定义&#xff1a; #include <time.h>:struct timespec {time_t t…...

【Element】el-form和el-table嵌套实现表格编辑并提交表单校验

一、背景 页面需要用到表格采集用户数据&#xff0c;提交时进行表单校验&#xff1b;即表格中嵌套着表单&#xff0c;保存时进行表单校验 二、功能实现 2.1、el-form和el-table嵌套说明 ① :model"formData" 给表单绑定数据&#xff0c;formData是表单的数据对象 …...

初识Winform

什么是winform&#xff1f; WinForms&#xff08;Windows Forms&#xff09;是Microsoft .NET框架中的一个用户界面&#xff08;UI&#xff09;技术&#xff0c;用于创建Windows应用程序。它提供了一组用于构建图形用户界面的类和控件&#xff0c;以及与用户交互的事件模型。 …...

Redis:原理速成+项目实战——Redis实战5(互斥锁、逻辑过期解决缓存击穿问题)

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;Redis&#xff1a;原理速成项目实战——Redis实战4&#xff08;解决Redis缓存穿透、雪崩、击穿&#xff09; &#x1f4da;订阅专…...

前端优化之一:dns预获取 dns-prefetch 提升页面载入速度

问题&#xff1a;怎么做到dns域解析&#xff1f; 用于优化网站页面的图片 问题&#xff1a;怎么提升网站性能&#xff1f; dns域解析&#xff0c;是提升网站的一个办法。 DNS Prefetch&#xff0c;即DNS预获取&#xff0c;是前端优化的一部分。 一般来说&#xff0c;在前端…...

C语言中一些基本数据类型的典型大小

char&#xff1a;通常是1字节。表示一个字符。int&#xff1a;通常在现代系统中是4字节&#xff08;但这取决于编译器和架构&#xff0c;有时可能是2字节&#xff09;。float&#xff1a;通常是4字节。double&#xff1a;通常是8字节。short 和 short int&#xff1a;通常是2字…...

[C/C++]排序算法 快速排序 (递归与非递归)

目录 &#x1f6a9;概念: &#x1f6a9;实现: ⚡1.hoare ⚡2.挖坑法 ⚡3.双指针法 &#x1f6a9;快速排序递归实现 &#x1f6a9;快速排序非递归实现 &#x1f6a9;概念: 通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所有数据比另一部分的所有…...

『年度总结』逐梦编程之始:我的2023学习回顾与展望

目录 前言 我与Python 我与C语言 第一篇正式博客&#xff1a; 第二篇正式博客&#xff08;扫雷&#xff09;&#xff1a; 指针学习笔记: C语言学习笔记&#xff1a; 我与数据结构&#xff1a; yuan 这篇博客&#xff0c;我将回顾2023年编程之旅的起点&#xff0c;同时展…...

MyBatis学习二:Mapper代理开发、配置文件完成增删改查、注解开发

前言 公司要求没办法&#xff0c;前端也要了解一下后端知识&#xff0c;这里记录一下自己的学习 学习教程&#xff1a;黑马mybatis教程全套视频教程&#xff0c;2天Mybatis框架从入门到精通 文档&#xff1a; https://mybatis.net.cn/index.html Mapper代理开发 目的 解决…...

【React系列】受控非受控组件

本文来自#React系列教程&#xff1a;https://mp.weixin.qq.com/mp/appmsgalbum?__bizMzg5MDAzNzkwNA&actiongetalbum&album_id1566025152667107329) 一. refs 的使用 在React的开发模式中&#xff0c;通常情况下不需要、也不建议直接操作DOM原生&#xff0c;但是某些…...

OpenCV-Python(22):2D直方图

目标 了解图像的2D直方图绘制2D直方图 介绍 在前面的部分我们介绍了如何绘制一维直方图&#xff0c;之所以称为一维&#xff0c;是因为我们只考虑了图像的一个特征&#xff1a;灰度值。但是在2D 直方图中我们就需要考虑两个图像特征。对于彩色图像的直方图通常情况下我们需要…...

Kubernetes 100个常用命令

本文简单总结关于使用 Kubectl 进行 Kubernetes 诊断的指南。列出了 100 个 Kubectl 命令&#xff0c;这些命令对于诊断 Kubernetes 集群中的问题非常有用。这些问题包括但不限于&#xff1a; 集群信息 Pod 诊断 服务诊断 部署诊断 网络诊断 持久卷和持久卷声明诊断 资源…...

labuladong日常刷题-差分数组 | LeetCode 1109航班预定统计 | 花式遍历 151反转字符串里的单词

差分数组–前缀和数组的升级 LeetCode 1109 航班预定统计 2024.1.1 题目链接labuladong讲解[链接] class Solution { public:vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {//构建航班人数数组&#xff0c;数组大小为n,初…...

HbuilderX中的git的使用

原文链接https://blog.csdn.net/Aom_yt/article/details/119924356...

LeetCode每日一题 | 1944. 队列中可以看到的人数

文章目录 队列中可以看到的人数题目描述问题分析程序代码&#xff08;Golang 版本&#xff09; 队列中可以看到的人数 题目描述 原题链接 有 n 个人排成一个队列&#xff0c;从左到右 编号为 0 到 n - 1 。给你以一个整数数组 heights &#xff0c;每个整数 互不相同&#xff…...

React16源码: JSX2JS及React.createElement源码实现

JSX 到 Javascript 的转换 React中的 JSX 类似于 Vue中的template模板文件&#xff0c;Vue是基于编译时将template模板转换成render函数在React中&#xff0c;JSX是类似于html和javascript混编的语法&#xff0c;而javascript是真的javascript, html并非真的html它的可阅读性可…...

整理composer安装版本的python脚本

整理composer安装版本的python脚本 脚本实现的功能是去除composer安装命令后的版本号 def remove_version_numbers(commands):"""Remove version numbers from composer require commands.Args:commands (list of str): List of composer require commands.Retu…...

十、基本对话框大集合(Qt5 GUI系列)

目录 一、设计需求 二、实现代码 三、代码解析 四、总结 一、设计需求 Qt提供了很多标准的对话框。例如标准文件对话框(QFileDialog)、标准颜色对话框(QColorDialog)、标准字体对话框 (QFontDialog)、标准输入对话框 (QInputDialog) 及消息对话框 (QMessageBox)。本文展示各…...

大A又跌了

才开盘几天&#xff0c;又开始下跌了。生活更加苦难。期待高深算法。...

This error originates from a subprocess, and is likely not a problem with pip

我遇这个问题是的原因是包名错误 注意检查包名...

数据库基础知识1

关系模型的程序员不需熟悉数据库的存取路径 在3层模式结构中,___I___是数据库的核心和关键,___Ⅱ___通常是模式的子集,数据库模式的描述提供给用户,____Ⅲ__的描述存储在硬盘上。Ⅰ.模式Ⅱ. 外模式Ⅲ. 内模式 数据库中,数据的物理独立性是指用户的应用程序与存储在磁盘上数据库…...

阿里云做网站号码/seo兼职工资一般多少

某明网络是一家创业公司&#xff0c;主营业务为盲盒电商。面试还没开始主要是一个笔试。但是笔试有三道题未写出来。 一 SpringBootApplication注解的组成 这道题比较简单&#xff0c;由三个注解组成&#xff0c;但是我忘了。忘了的原因是什么呢&#xff1f;是没有形成长时记忆…...

wordpress oss静态/安装百度一下

文章目录前言一、收货地址功能实现二、效果前言 在电商系统中&#xff0c;收货地址是必不可少的功能&#xff0c;没有收货地址用户在下单就没法收到货&#xff0c;而且一个用户会有多个收货地址&#xff0c;比如寄给自己&#xff0c;或者寄给别人。一搬在收货地址选择中会有个…...

wordpress显示缩略图 摘要/360站长工具seo

作为讲述口袋妖怪的Round 16&#xff0c;这里&#xff0c;我会采用“夹叙夹议&#xff0c;夹议夹叙”的模式进行编排。也就是在议论一些口袋妖怪中的小游戏的核心算法的同时&#xff0c;叙述一下我对口袋妖怪的理解以及我与这一系列的经历。以上&#xff0c;就是我们的那位少年…...

网站设计hb软件/网页搭建

MBR分区表模式&#xff1a;MBR分区的分区表保存在硬盘的第一个扇区&#xff0c;而且只有64字节&#xff0c;所以最多只能有四个表项。也就是说&#xff0c;我们只能把硬盘分为4主分区&#xff0c;或者分成小于等于3个主分区再加一个扩展分区。扩展分区又可以分为多个逻辑分区。…...

苏州企业网站建设开发与制作/都有什么推广平台

最近用ThinkPHP做了一个邮箱找回密码功能&#xff0c;在遭遇了N个bug之后终于做成了&#xff0c;下面分享一下邮箱找回密码功能的实现&#xff1a; 邮箱找回密码实际上就是在用户通过验证之后重置密码的过程&#xff0c;一般开发者会在验证用户信息后通过程序生成一个新密码 或…...

wordpress 微软雅黑/seo网站优化推广教程

首先&#xff0c;电子商务设计师属于软考中级&#xff0c;因此难度也不是特别大。但并不是说就完全没有难度&#xff0c;难度还是有的&#xff0c;像上午题一般把基本知识点掌握了&#xff0c;是没什么问题的&#xff0c;重点就在于下午题会比较难。 接下来我们来剖析一下考试…...