动态规划-入门三道题

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

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

第10章 中断和动态时钟显示

第10章 中断和动态时钟显示 从本章开始,按照书籍的划分,第10章开始就进入保护模式(Protected Mode)部分了,感觉从这里开始难度突然就增加了。 书中介绍了为什么有中断(Interrupt)的设计,中断的几种方式:外部硬件中断、内部中断和软中断。通过中断做了一个会走的时钟和屏幕上输入字符的程序。 我自己理解中断的一些作用: 为了更好的利用处理器的性能。协同快速和慢速设备一起工作

动态规划---打家劫舍

题目: 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。 思路: 动态规划五部曲: 1.确定dp数组及含义 dp数组是一维数组,dp[i]代表

uva 10055 uva 10071 uva 10300(水题两三道)

情歌两三首,水题两三道。 好久没敲代码了为暑假大作战热热身。 uva 10055 Hashmat the Brave Warrior 求俩数相减。 两个debug的地方,一个是longlong,一个是输入顺序。 代码: #include<stdio.h>int main(){long long a, b;//debugwhile(scanf("%lld%lld", &

数论入门整理(updating)

一、gcd lcm 基础中的基础,一般用来处理计算第一步什么的,分数化简之类。 LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } <pre name="code" class="cpp">LL lcm(LL a, LL b){LL c = gcd(a, b);return a / c * b;} 例题:

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

Java 创建图形用户界面(GUI)入门指南(Swing库 JFrame 类)概述

概述 基本概念 Java Swing 的架构 Java Swing 是一个为 Java 设计的 GUI 工具包,是 JAVA 基础类的一部分,基于 Java AWT 构建,提供了一系列轻量级、可定制的图形用户界面(GUI)组件。 与 AWT 相比,Swing 提供了许多比 AWT 更好的屏幕显示元素,更加灵活和可定制,具有更好的跨平台性能。 组件和容器 Java Swing 提供了许多

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al