动态规划-入门三道题

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

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》:本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat

解析C++11 static_assert及与Boost库的关联从入门到精通

《解析C++11static_assert及与Boost库的关联从入门到精通》static_assert是C++中强大的编译时验证工具,它能够在编译阶段拦截不符合预期的类型或值,增强代码的健壮性,通... 目录一、背景知识:传统断言方法的局限性1.1 assert宏1.2 #error指令1.3 第三方解决

springboot如何通过http动态操作xxl-job任务

《springboot如何通过http动态操作xxl-job任务》:本文主要介绍springboot如何通过http动态操作xxl-job任务的问题,具有很好的参考价值,希望对大家有所帮助,如有错... 目录springboot通过http动态操作xxl-job任务一、maven依赖二、配置文件三、xxl-

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么?能干嘛?核心作用:二、索引的 4 种主要类型(附通俗例子)1. BTree 索引(

Redis 配置文件使用建议redis.conf 从入门到实战

《Redis配置文件使用建议redis.conf从入门到实战》Redis配置方式包括配置文件、命令行参数、运行时CONFIG命令,支持动态修改参数及持久化,常用项涉及端口、绑定、内存策略等,版本8... 目录一、Redis.conf 是什么?二、命令行方式传参(适用于测试)三、运行时动态修改配置(不重启服务

MySQL DQL从入门到精通

《MySQLDQL从入门到精通》通过DQL,我们可以从数据库中检索出所需的数据,进行各种复杂的数据分析和处理,本文将深入探讨MySQLDQL的各个方面,帮助你全面掌握这一重要技能,感兴趣的朋友跟随小... 目录一、DQL 基础:SELECT 语句入门二、数据过滤:WHERE 子句的使用三、结果排序:ORDE

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. 灵活性与可