代码学习记录31---动态规划开始

随想录日记part31

t i m e : time: time 2024.03.29



主要内容:今天开始要学习动态规划的相关知识了,今天的内容主要涉及四个方面:
理论基础 ; 斐波那契数 ;爬楼梯 ;使用最小花费爬楼梯。

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


关于动态规划的理论知识,我们可以直接去看 理论基础 对应的链接就可以了。下面主要还是对于题目的讲解。在这里插入图片描述
总结一下核心思想:

对于动态规划问题,我将拆解为如下五步曲,这五步都搞清楚了,才能说把动态规划真的掌握了!
【1】.确定dp数组以及下标的含义
【2】.确定递推公式
【3】.dp数组如何初始化
【4】.确定遍历顺序
【5】.举例推导dp数组

Topic1斐波那契数

题目:

斐波那契数 (通常用 F ( n ) F(n) F(n) 表示)形成的序列称为斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:
F ( 0 ) = 0 , F ( 1 ) = 1 F(0) = 0,F(1) = 1 F(0)=0F(1)=1
F ( n ) = F ( n − 1 ) + F ( n − 2 ) F(n) = F(n - 1) + F(n - 2) F(n)=F(n1)+F(n2),其中 n > 1 n > 1 n>1
给定 n n n ,请计算 F ( n ) F(n) F(n)

输入: n = 4 n = 4 n=4
输出: 3 3 3
解释: F ( 4 ) = F ( 3 ) + F ( 2 ) = 2 + 1 = 3 F(4) = F(3) + F(2) = 2 + 1 = 3 F(4)=F(3)+F(2)=2+1=3

思路:

按照上面的五个步骤给出下面的代码:
代码如下:

class Solution {
    public int fib(int n) {
        // 【1】.确定dp数组以及下标的含义
        int[] dp = new int[n + 1];// dp[n]就是第i个数的斐波那契数值
        // 【3】.dp数组如何初始化
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        dp[0] = 0;
        dp[1] = 1;
        // 【2】.确定递推公式【4】.确定遍历顺序【5】.举例推导dp数组
        for (int i = 2; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)



Topic2爬楼梯

题目:

假设你正在爬楼梯。需要 n n n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

输入: n = 3 n = 3 n=3
输出: 3 3 3
解释:
有三种方法可以爬到楼顶。
【1】.1 阶 + 1 阶 + 1 阶
【2】. 1 阶 + 2 阶
【3】. 2 阶 + 1 阶
思路:

按照上面的五个步骤给出下面的代码,在注释中给出具体的思路:
整体代码如下:

class Solution {
    public int climbStairs(int n) {
        // 【1】.确定dp数组以及下标的含义,这里的dp[i]表示i阶到达楼顶的方法数
        int[] dp = new int[n + 1];
        // 【3】.dp数组如何初始化
        if (n == 1)
            return 1;
        if (n == 2)
            return 2;
        dp[1] = 1;
        dp[2] = 2;
        // 【2】.确定递推公式dp[i]=dp[i-1]+dp[i-2];【4】.确定遍历顺序【5】.举例推导dp数组
        for (int i = 3; i < n + 1; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)



Topic3使用最小花费爬楼梯

题目:

给你一个整数数组 c o s t cost cost ,其中 c o s t [ i ] cost[i] cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。

输入: c o s t = [ 10 , 15 , 20 ] cost = [10,15,20] cost=[10,15,20]
输出: 15 15 15
解释: 你将从下标为 1 的台阶开始。支付 15 ,向上爬两个台阶,到达楼梯顶部。
总花费为 15 。

思路:

举例推导dp数组
拿示例: c o s t = [ 1 , 100 , 1 , 1 , 1 , 100 , 1 , 1 , 100 , 1 ] cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] cost=[1,100,1,1,1,100,1,1,100,1] ,来模拟一下 d p dp dp 数组的状态变化,如下:
在这里插入图片描述

整体代码如下:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        // 【1】.确定dp数组以及下标的含义
        // dp[i]表示到达第i个台阶的最低花费钱数
        int n = cost.length;
        int[] dp = new int[cost.length + 1];
        // 【3】.dp数组如何初始化【4】.确定遍历顺序
        dp[0] = 0;
        dp[1] = 0;
        // 【2】.确定递推公式//【4】.确定遍历顺序//【5】.举例推导dp数组
        for (int i = 2; i < n + 1; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

平价运动型蓝牙耳机哪个牌子好?精心筛选五大必购产品分享!

蓝牙耳机已成为现代人生活中不可或缺的一部分&#xff0c;特别是那些追求健康、热爱运动的朋友们&#xff0c;平价且实用的运动型蓝牙耳机更是他们的首选&#xff0c;在众多的品牌与型号中&#xff0c;如何选择一款既符合预算又满足运动需求的蓝牙耳机呢&#xff1f;今天就让我…

个人优势能力测评,寻找你的天赋

个人优势能力测评&#xff0c;用来发现自己的天赋&#xff0c;也被称之为多元智力测评&#xff0c;该理论认为人的智力不仅仅是逻辑思维能力&#xff0c;每个人的天赋不同&#xff0c;具有多样性&#xff0c;目前的智力测试基本上都以逻辑思维&#xff0c;推理能力为主&#xf…

C++项目——集群聊天服务器项目(九)客户端异常退出业务

服务器端应检测到客户端是否异常退出&#xff0c;因此本节来实现客户端异常退出&#xff0c;项目流程见后文 一、客户端异常退出业务流程 &#xff08;1&#xff09;在业务模块定义处理客户端异常退出的函数 &#xff08;2&#xff09;集群聊天服务器项目(八&#xff09;提到…

剑指Offer题目笔记23(归并排序)

面试题77&#xff1a; 问题&#xff1a; ​ 输入一个链表的头节点&#xff0c;将该链表排序。 解决方案&#xff1a; ​ 使用归并排序。将链表分为两个子链表&#xff0c;在对两个子链表排序后再将它们合并为一个排序的链表。 源代码&#xff1a; /*** Definition for sin…

Python循环语句for

主要解决什么样的问题&#xff1a;具有重复性、规律性的问题 循环四要素&#xff1a; 循环的开始&#xff08;从第1步开始&#xff1b;从第1步开始/从起点开始&#xff09; 循环的继续条件&#xff08;还没走到第10步&#xff1b;没有碰到墙/就是看距离&#xff09; 循环体&…

算法学习——LeetCode力扣动态规划篇4

算法学习——LeetCode力扣动态规划篇4 377. 组合总和 Ⅳ 377. 组合总和 Ⅳ - 力扣&#xff08;LeetCode&#xff09; 描述 给你一个由 不同 整数组成的数组 nums &#xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保…

JSQLParserException异常

前言 SQL中加入了租户字段&#xff0c;报这个错&#xff0c;可以查出数据&#xff0c;但是不多&#xff1b;SQL检查无问题 解决 原因一 引入新的SQL解析器检查解析SQL&#xff0c;与mybatis多租户无关 参考 <!--jsqlparser版本太低也无法解析&#xff0c;如2.0--> &…

左侧或水平导航菜单栏与main区域联动

系列文章目录 一、elementui 导航菜单栏和Breadcrumb 面包屑关联 二、左侧导航菜单栏与main区域联动 文章目录 系列文章目录前言一、实现步骤1.<el-menu>中设置属性router为true2.<el-menu-item>中设置路由 route"/"3.<el-main>里设置路由出口4…

Android Studio Iguana | 2023.2.1 补丁 1

Android Studio Iguana | 2023.2.1 Canary 3 已修复的问题Android Gradle 插件 问题 295205663 将 AGP 从 8.0.2 更新到 8.1.0 后&#xff0c;任务“:app:mergeReleaseClasses”执行失败 问题 298008231 [Gradle 8.4][升级] 由于使用 kotlin gradle 插件中已废弃的功能&#…

游戏行业行业竞争越来越激烈,遇到DDoS攻击遭受严重损失该如何解决

近年来&#xff0c;我们见证了数字化的快速发展&#xff0c;随着这样的发展&#xff0c;网络的威胁也逐渐增多&#xff0c;在网络攻击门槛不断降低&#xff0c;行业竞争越来越激烈&#xff0c;游戏行业的DDoS攻击如雨点般密集&#xff0c;在整个DDoS攻击的份额中&#xff0c;游…

C语言goto语句介绍

在C语言中&#xff0c;goto语句是一种流程控制语句&#xff0c;用于无条件地转移到程序中的特定标签位置。尽管goto语句在编程中具有一定的争议&#xff0c;但在某些情况下&#xff0c;它可以提供一种简单有效的解决方案。本文将深入介绍C语言中的goto语句&#xff0c;包括其基…

android安卓英语学习课设

一、关于这个项目ELAPP 该项目是一个基于java开发的服务器-客户端模式的安卓英语学习软件&#xff0c;主要功能点就是背单词&#xff0c;中英文翻译&#xff0c;OCR文字翻译。 服务器端使用springboot&#xff0c;mybatisplus&#xff0c;MySQL&#xff0c;mongodb&#xff0…

Solo 开发者周刊 (第9期):Dawwin首位人工智能编程师或将改变未来?

这里会整合 Solo 社区每周推广内容、产品模块或活动投稿&#xff0c;每周五发布。在这期周刊中&#xff0c;我们将深入探讨开源软件产品的开发旅程&#xff0c;分享来自一线独立开发者的经验和见解。本杂志开源&#xff0c;欢迎投稿。 好文推荐 Dawwin首位人工智能编程师&#…

企业数据被新型.rmallox勒索病毒加密,应该如何还原?

.rmallox勒索病毒为什么难以解密&#xff1f; .rmallox勒索病毒难以解密的主要原因在于其采用了高强度的加密算法&#xff0c;并且这些算法被有效地实施在了病毒程序中。具体来说&#xff0c;.rmallox勒索病毒使用了RSA和AES这两种非常成熟的加密算法。RSA是一种非对称加密算法…

linux安装Tomcat

linux安装Tomcat 下载地址&#xff1a;https://archive.apache.org/dist/tomcat/tomcat-8/v8.5.87/bin/apache-tomcat-8.5.87.tar.gz 将下载的安装包传到该文件夹 解压安装包 tar -zxvf apache-tomcat-8.5.87.tar.gz 配置环境变量 vim /etc/profile 添加指定文件最下方 expo…

【编程笔记】学会使用 Git

目录 一、介绍 Git二、安装 Git三、 常用 linux 目录四、Git 的必要配置(1) 查看和删除之前的配置(2) 配置 Git 五、Git 基本理论六、Git 项目搭建七、Git 文件操作八、分支Git 笔记 ❀❀❀(1) 常规使用(2) 分支 一、介绍 Git &#x1f4d6; VCS&#xff1a;Version Control S…

第六讲 B+树索引

1 B树大家庭 有一种称为 B 树的特定数据结构&#xff0c;人们还使用该术语来泛指一类平衡树数据结构&#xff1a; B-Tree (1971)BTree (1973)B*Tree (1977?)B link-Tree (1981)Bε-Tree (2003)Bw-Tree (2013) 2 B树 BTree 是一种自平衡【self-balance】、有序【ordered】的…

JavaEE 初阶篇-深入了解多线程安全问题(出现线程不安全的原因与解决线程不安全的方法)

&#x1f525;博客主页&#xff1a; 【小扳_-CSDN博客】 ❤感谢大家点赞&#x1f44d;收藏⭐评论✍ 文章目录 1.0 多线程安全问题概述 1.1 线程不安全的实际例子 2.0 出现线程不安全的原因 2.1 线程在系统中是随机调度且抢占式执行的模式 2.2 多个线程同时修改同一个变量 2.3 线…

C语言-编译和链接

目录 1.前言2.编译2.1预处理&#xff08;预编译&#xff09;2.1.1 #define 定义常量2.1.2 #define 定义宏2.1.3带有副作用的宏参数2.1.4宏替换规则2.1.5 #和##2.1.5.1 #运算符2.1.5.2 ## 运算符 2.1.6 命名约定2.1.7 #undef2.1.8 条件编译2.1.9 头文件的包含2.1.9.1 本地文件包…