代码随想录算法训练营第三十八天|理论基础、509. 斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯

news/2024/4/23 20:19:01/

文章目录

      • 理论基础
      • 509. 斐波那契数
      • 70. 爬楼梯
      • 746. 使用最小花费爬楼梯

理论基础

  • 动态规划-DP

    1. 动态规划中每一个状态一定是由上一个状态推导出来的,这一点就区分于贪心,贪心没有状态推导,而是从局部直接选最优的

    2. 背包问题:
      动态规划中dp[j]是由dp[j-weight[i]]推导出来的,然后取max(dp[j], dp[j - weight[i]] + value[i])。
      但如果是贪心呢,每次拿物品选一个最大的或者最小的就完事了,和上一个状态没有关系。

  • 动规五步

    1. 确定dp数组(dp table)以及下标的含义

    2. 确定递推公式

    3. dp数组如何初始化

    4. 确定遍历顺序

    5. 举例推导dp数组

509. 斐波那契数

  • 解题思路:
    1.确定递推公式 => dp[i] = dp[i - 1] + dp[i - 2];
    2.确定遍历顺序 => 从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],
    那么遍历的顺序一定是从前到后遍历的
    3.举例推导dp数组
public int fib(int n) {if(n <= 1){return n;}int[] dp = new int[2];dp[0] = 0;dp[1] = 1;int sum = 0;for (int i = 2; i <= n; i++) {sum = dp[0] + dp[1];dp[0] = dp[1];dp[1] = sum; }return sum;
}

70. 爬楼梯

  • 解题思路:
    ①确定dp数组:dp[i]: 爬到第i层楼梯,有dp[i]种方法
    ②递推公式:dp[i] = dp[i - 1] + dp[i - 2],dp[i - 1],上i-1层楼梯,有dp[i - 1]种方法;
    dp[i - 2],上i-2层楼梯,有dp[i - 2]种方法
    在推导dp[i]的时候,一定要时刻想着dp[i]的定义,否则容易跑偏
    ③初始化:不考虑dp[0]如何初始化,只初始化dp[1] = 1,dp[2] = 2,然后从i = 3开始递推,这样才符合dp[i]的定义
    ④遍历顺序:从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,遍历顺序一定是从前向后遍历的
public int climbStairs(int n) {if(n <= 1){return n;}//dp数组int[] dp = new int[n + 1];//初始化dp[1] = 1;dp[2] = 2;//遍历for (int i = 3; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];
}

746. 使用最小花费爬楼梯

  • 解题思路:
    1.dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]。
    2.确定递推公式:可以有两个途径得到dp[i],一个是dp[i-1] 一个是dp[i-2]
    dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
    3.dp数组如何初始化, dp[0] = 0,dp[1] = 0; 到达 第 0 个台阶是不花费的
    4.确定遍历顺序,从前向后遍历
public int minCostClimbingStairs(int[] cost) {//不用加判断// if(cost.length == 2){//     return 0;// }//注意:最后一步也要花费//dp数组int[] dp = new int[cost.length + 1];//初始化dp[0] = 0;dp[1] = 0;//遍历for (int i = 2; i <= cost.length; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.length];
}

http://www.ppmy.cn/news/48271.html

相关文章

Progress ThemeBuilder crack

Progress ThemeBuilder crack 自定义输入将覆盖自定义日期输入和下拉列表。 Fluent主题中的图表不应用系列颜色。 撤消重做操作会导致重复以前编辑过的变量。 拆分器折叠的拆分条模板错误。 ThemeBuilder是一个多功能工具&#xff0c;可以帮助您创建视觉样式&#xff0c;并将其…

Redis缓存MySQL数据库存储二者如何保证数据一致性

文章目录 Redis缓存MySQL数据库存储二者如何保证数据一致性数据一致性问题缓存穿透缓存雪崩 Redis缓存MySQL数据库存储一致性解决方案方案一&#xff1a;读写数据库时同步更新缓存方案二&#xff1a;使用消息队列异步更新缓存 总结 Redis缓存MySQL数据库存储二者如何保证数据一…

背锅侠?软件测试各类bug分类定位,从功能到性能超细总结......

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 遇到功能性问题&a…

软件测试概念篇(下)|开发模型与测试模型

作者&#xff1a;爱塔居 专栏&#xff1a;软件测试 作者简介&#xff1a;大三学生&#xff0c;希望同大家一起进步&#xff01; 文章简介&#xff1a;主要介绍软件生命周期、瀑布模型和螺旋模型两个开发模型&#xff0c;V模型和W模型两个测试模型 文章目录 目录 文章目录 一、软…

IOC容器与DI依赖注入示例

IOC容器与DI依赖注入示例 IOC深入理解IOC示例&#xff1a; DI深入理解DI示例 IOC深入理解 我们先通过几个问题来加深一下对IOC的理解 (1)Spring是使用IOC容器来管理bean对象的&#xff0c;我们主要管理什么? 主要管理项目中所使用到的类对象&#xff0c;比如(Service层对像和…

在现成的3D打印机上进行实验理论:一种数据孪生的攻击探测框架

在现成的3D打印机上提供了一种DT中攻击探测框架的DT解决方案的实验演示&#xff0c;作为说明性CPMS资源。通过网络安全DT对打印机正常运行、异常运行和攻击三种情况下的实验数据进行收集和分析&#xff0c;得出攻击检测结果。实验装置概述如下图所示。该实验研究是在现实世界设…

tokenURI的实现方式

做数字藏品最重要的function是tokenURI(tokenId)。 实现1 基本路径tokenID ERC721 function tokenURI(uint256 tokenId) public view virtual override returns (string memory) {_requireMinted(tokenId);string memory baseURI _baseURI();return bytes(baseURI).length &…

HarmonyOS原子化服务卡片整改、下架、升级失败部分原因及处理办法

随着HarmonyOS应用体系相关规则、团队的不断发展和完善&#xff0c;早期上架运营的HarmonyOS原子化服务卡片&#xff0c;很多都收到了整改、下架的通知&#xff0c;主要集中在用户协议、隐私声明、服务卡片的设计规范性等细节方面的问题&#xff1b;需要进行优化调整升级才行。…

源码:LeakCanary

一、介绍 自动检测内存泄漏的检查工具 二、使用 debugImplementation com.squareup.leakcanary:leakcanary-android:2.5debugImplementation只在debug模式的编译和最终的debug apk打包时有效 Memory Profiler 使用步骤 生成的内存泄漏快照 会放在sdcard/Download/leakcanar…

SSR在天猫优品大促会场的探索实践

BBC 发现其网站加载时间每增加一秒&#xff0c;用户便会流失 10%。为提高页面的秒开率&#xff0c;我们不断探索着优化策略&#xff0c;仅仅在浏览器领域下的优化已经满足不了我们的极致要求&#xff0c;开始往服务端方向不断探索。本文将讨论业务接入SSR的几个问题&#xff1a…

Spring Security --- formLogin配置

目录 环境准备 配置自定义登录表单页面 配置登录成功的跳转页面方式 配置登录失败的跳转页面方式 前端表单参数获取 CustomWebSecurityConfigurerAdapter配置类代码示例 环境准备 创建springboot项目引入spring security框架引入thymeleaf模板引擎 配置自定义登录表单页面…

水平居中、垂直居中的几种方法

水平居中的方法&#xff1a; 若是针对inline, 内联块inline-block, 内联表inline-table, inline-flex元素及img,span,button等元素 父元素设置 text-align:center; 绝对定位&#xff1b;弹性布局&#xff1b;grid网格布局 不定宽块状元素 设置 margin&#xff1a;auto; 绝对定…

第二章:uniapp整合axios之真机测试两问题

第二章&#xff1a;uniapp整合axios之真机测试两问题 上一章节&#xff0c;笔者编写了uniapp整合axios并实现前后端跨域请求的方案&#xff0c;完成了这些基本配置后&#xff0c;在浏览器端的测试基本是可以完成了&#xff0c;但是当笔者将程序运行到手机时&#xff0c;却出现…

springboot mybatis-plus 对接 sqlserver 数据库 批处理的问题 批量更新添加数据 方案三

问题&#xff1a; 在对接 sqlserver数据库的时候 主子表 保存的时候 子表批量保存 使用的 mybatis-plus提供的 saveOrUpdateBatch saveBatch 这两个方法 但是 报错 报错内容为 &#xff1a; com.microsoft.sqlserver.jdbc.SQLServerException: 必须执行该语句才能获得结果。 框…

springboot web项目统一时区方案

背景 springboot项目国际化中&#xff0c;会遇到用户选择的时间和最终存到数据库的时间不一致&#xff0c;可能就是项目开发和部署时的时区没有处理好&#xff0c;导致时间转换出现了问题。 先了解时区都有哪些&#xff1a; 1.GMT&#xff1a;Greenwich Mean Time 格林威治…

Kubernetes Operator开发

案例一 Traefik Operator开发 1.kubebuilder 创建项目 2.Crontroller开发与部署 开发环境准备 kubebuilder 介绍 CRD的开发与部署 Crontroller开发与部署 Operator功能设计 借助operator完成 和企业内部注册中心打通 这里以Traefiketcd的模式为例进行演示说明 在这里etcd p…

1.2和1.3、GCC

1.2和1.3、GCC 1.2和1.3、GCC1.2.1、什么是GCC1.2.2、编程语言的发展1.2.3、GCC工作流程1.2.4、gcc和g的区别1.2.5、GCC常用参数选项实际操作①接下来进行预处理操作&#xff08;test.c为需要预处理的源代码&#xff0c;test.i为要生成的目标代码&#xff09;②汇编操作&#x…

多线程基础

1.多线程基础概念 多线程&#xff1a;让程序同时做多件事情 多线程作用&#xff1a;提高效率 并发&#xff1a;在同一时间&#xff0c;有多个指令在单个cpu上交替执行 并行&#xff1a;在同一时刻&#xff0c;有多个指令在多个cpu上同时执行 2.多线程的实现 (1)继承Thread类…

电脑卡顿反应慢怎么处理?电脑提速,4个方法!

案例&#xff1a;电脑卡顿反应慢怎么处理&#xff1f; 【快帮帮我&#xff01;我的电脑现在越用越卡了&#xff0c;有时候光是打开一个文件都要卡好几分钟&#xff0c;我真的太难了&#xff0c;有什么可以加速电脑反应速度的好方法吗&#xff1f;万分感谢&#xff01;】 随着…

es7.x集群部署-多台物理机部署-docker环境部署-docker-compose管理

es集群部署文档 部署es服务的三台服务器的ip和host分分别是&#xff1a; iphost_name192.168.1.2web02192.168.1.3storage02192.168.1.4Storage03 这个配置需要在服务器上编写对应的hosts文件&#xff0c;然后才可以使用host进行配置。 本次部署没有外挂配置文件&#xff0…