动态规划-入门三道题

2024-04-12 10:28
文章标签 动态 规划 入门 三道

本文主要是介绍动态规划-入门三道题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1137. 第 N 个泰波那契数

题目描述:
在这里插入图片描述
状态表示:
dp[i]表示第i个泰波那契数。
状态转移方程:
dp[i]=dp[i-3]+dp[i-2]+dp[i-1]。
初始化:
动态规划问题的初始化就是为了去避免初始情况下的越界问题。这里就对dp[0]=0,dp[1]=1,dp[2]=1这样进行初始化即可,题目已经给出了,非常简单。
填表顺序:
显而易见填表顺序为从左到右。
返回值:
因为dp[i]表示第i个泰波那契数,题目要求计算第n个斐波那契数,因此返回dp[n]即可。
代码如下:
经过以上过程之后编写代码还要注意一个细节,注意要提前根据n的大小进行判断,如果数组大小小于等于2但是未经过判断,后面的初始化就会出现越界问题。

class Solution {public int tribonacci(int n) {int[] dp = new int[n + 1];if (n == 0) {return 0;}if (n == 1) {return 1;}if (n == 2) {return 1;}dp[0] = 0;dp[1] = 1;dp[2] = 1;for (int i = 3; i <= n; i++) {dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];}return dp[n];}
}

题目链接
时间复杂度:O(n)
空间复杂度:O(n)
空间优化版本:

class Solution {public int tribonacci(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}if (n == 2) {return 1;}int num1 = 0;int num2 = 1;int num3 = 1;int num4 = 0;for (int i = 0; i <= n - 3; i++) {num4 = num1 + num2 + num3;num1 = num2;num2 = num3;num3 = num4;}return num3;}
}

面试题 08.01. 三步问题

题目描述:
在这里插入图片描述
状态表示:
dp[i]表示达到第i阶台阶有多少种方法。
状态转移方程:
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]。
初始化:
还是为了防止越界,初始化dp[1]=0,dp[2]=2,dp[0]=1。
填表顺序:
从左至右。
返回值:
返回dp[n]。
代码如下:

class Solution {public int waysToStep(int n) {int[] dp = new int[n + 1];if (n == 0 || n == 1) {return 1;}if (n == 2) {return 2;}dp[0] = 1;dp[1] = 1;dp[2] = 2;int MOD = (int) 1e9 + 7;for (int i = 3; i <= n; i++) {dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;}return dp[n];}
}

题目链接
时间复杂度:O(n)
空间复杂度:O(n)

746. 使用最小花费爬楼梯

题目描述:
在这里插入图片描述
状态表示:
第一种方法,dp[i]表示到达第i个台阶使用的最低费用。
第二种方法,dp[i]表示从第i个台阶到达最顶部的最低费用。
状态转移方程:
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])。
dp[i]=min(dp[i+1]+dp[i+2])+cost[i]。
初始化:
方法一要避免越界,初始化dp[0]=0,dp[1]=0。
方法二要避免越界,初始化dp[n-1]=cost[i],dp[n]=0。
填表顺序:
方法一从左至右,方法二从右至左。
返回值:
方法一返回值为dp[n],这里的n是cost数组的长度。
方法二返回值为min(dp[0],dp[1])。
方法一代码如下:

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n + 1];for (int i = 2; i <= n; i++) {dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[n];}}

方法二代码如下:

class Solution {public int minCostClimbingStairs(int[] cost) {int n = cost.length;int[] dp = new int[n + 1];dp[n] = 0;dp[n - 1] = cost[n - 1];for (int i = n - 2; i >= 0; i--) {dp[i] = Math.min(dp[i + 1], dp[i + 2]) + cost[i];}return Math.min(dp[0], dp[1]);}}

题目链接
方法一和方法二的时空复杂度相同如下:
时间复杂度:O(n)
空间复杂度:O(n)

这篇关于动态规划-入门三道题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

Java调用C#动态库的三种方法详解

《Java调用C#动态库的三种方法详解》在这个多语言编程的时代,Java和C#就像两位才华横溢的舞者,各自在不同的舞台上展现着独特的魅力,然而,当它们携手合作时,又会碰撞出怎样绚丽的火花呢?今天,我们... 目录方法1:C++/CLI搭建桥梁——Java ↔ C# 的“翻译官”步骤1:创建C#类库(.NET

MyBatis编写嵌套子查询的动态SQL实践详解

《MyBatis编写嵌套子查询的动态SQL实践详解》在Java生态中,MyBatis作为一款优秀的ORM框架,广泛应用于数据库操作,本文将深入探讨如何在MyBatis中编写嵌套子查询的动态SQL,并结... 目录一、Myhttp://www.chinasem.cnBATis动态SQL的核心优势1. 灵活性与可

Python中OpenCV与Matplotlib的图像操作入门指南

《Python中OpenCV与Matplotlib的图像操作入门指南》:本文主要介绍Python中OpenCV与Matplotlib的图像操作指南,本文通过实例代码给大家介绍的非常详细,对大家的学... 目录一、环境准备二、图像的基本操作1. 图像读取、显示与保存 使用OpenCV操作2. 像素级操作3.

Mybatis嵌套子查询动态SQL编写实践

《Mybatis嵌套子查询动态SQL编写实践》:本文主要介绍Mybatis嵌套子查询动态SQL编写方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言一、实体类1、主类2、子类二、Mapper三、XML四、详解总结前言MyBATis的xml文件编写动态SQL

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

golang实现动态路由的项目实践

《golang实现动态路由的项目实践》本文主要介绍了golang实现动态路由项目实践,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习... 目录一、动态路由1.结构体(数据库的定义)2.预加载preload3.添加关联的方法一、动态路由1

Python Selenium动态渲染页面和抓取的使用指南

《PythonSelenium动态渲染页面和抓取的使用指南》在Web数据采集领域,动态渲染页面已成为现代网站的主流形式,本文将从技术原理,环境配置,核心功能系统讲解Selenium在Python动态... 目录一、Selenium技术架构解析二、环境搭建与基础配置1. 组件安装2. 驱动配置3. 基础操作模

POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能

《POI从入门到实战轻松完成EasyExcel使用及Excel导入导出功能》ApachePOI是一个流行的Java库,用于处理MicrosoftOffice格式文件,提供丰富API来创建、读取和修改O... 目录前言:Apache POIEasyPoiEasyExcel一、EasyExcel1.1、核心特性

慢sql提前分析预警和动态sql替换-Mybatis-SQL

《慢sql提前分析预警和动态sql替换-Mybatis-SQL》为防止慢SQL问题而开发的MyBatis组件,该组件能够在开发、测试阶段自动分析SQL语句,并在出现慢SQL问题时通过Ducc配置实现动... 目录背景解决思路开源方案调研设计方案详细设计使用方法1、引入依赖jar包2、配置组件XML3、核心配

Python中模块graphviz使用入门

《Python中模块graphviz使用入门》graphviz是一个用于创建和操作图形的Python库,本文主要介绍了Python中模块graphviz使用入门,具有一定的参考价值,感兴趣的可以了解一... 目录1.安装2. 基本用法2.1 输出图像格式2.2 图像style设置2.3 属性2.4 子图和聚