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

本文主要是介绍代码随想录算法训练营第38天|● 理论基础 ● 509. 斐波那契数● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

动态规划理论基础

动态规划,英文:Dynamic Programming,简称DP,如果某一问题有很多重叠子问题,使用动态规划是最有效的。

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


动态规划做题步骤

  1. 确定dp数组(dp table)以及下标的含义
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序
  5. 举例推导dp数组

动态规划做题debug

  1. 找问题的最好方式就是把dp数组打印出来
  2. 做动规的题目,写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍,心中有数,确定最后推出的是想要的结果

斐波那契数

509. 斐波那契数 - 力扣(LeetCode)

本题为动态规划入门题,根据题目进行模拟即可

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

dp[i]的定义为:第i个数的斐波那契数值是dp[i]

2.确定递推公式

为什么这是一道非常简单的入门题目呢?

因为题目已经把递推公式直接给我们了:状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3.dp数组如何初始化

题目中把如何初始化也直接给我们了,如下:

arr[0]=0;

arr[1]=1;

4.确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出,dp[i]是依赖 dp[i - 1] 和 dp[i - 2],那么遍历的顺序一定是从前到后遍历的

class Solution {public int fib(int n) {if (n <= 1) {return n;}int[] arr = new int[2];arr[0] = 0;arr[1] = 1;for (int i = 2; i <= n; i++) {int sum = arr[0] + arr[1];arr[0] = arr[1];arr[1] = sum;}return arr[1];}
}

爬楼梯

70. 爬楼梯 - 力扣(LeetCode)

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

          到达第i 层有dp[i]种方法

      2.确定递推公式

           dp[i]=dp[i-1]+dp[i-2]

      3.dp数组如何初始化

           dp[1]=1;  

          dp[2]=1;

     4.确定遍历顺序

         从前向后遍历

代码:

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

使用最小花费爬楼梯 

746. 使用最小花费爬楼梯 - 力扣(LeetCode)

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

    dp[i]的定义:到达第i台阶所花费的最少体力为dp[i]。  

2.确定递推公式

      dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

     dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

    那么dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

3.dp数组初始化

由题目可以知道你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。所以从0或1开始不需要花钱

dp[0]=0;dp[1]=0;

4.遍历顺序

从前向后

class Solution {public int minCostClimbingStairs(int[] cost) {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];}
}

这篇关于代码随想录算法训练营第38天|● 理论基础 ● 509. 斐波那契数● 70. 爬楼梯 ● 746. 使用最小花费爬楼梯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1070915

相关文章

Python使用FFmpeg实现高效音频格式转换工具

《Python使用FFmpeg实现高效音频格式转换工具》在数字音频处理领域,音频格式转换是一项基础但至关重要的功能,本文主要为大家介绍了Python如何使用FFmpeg实现强大功能的图形化音频转换工具... 目录概述功能详解软件效果展示主界面布局转换过程截图完成提示开发步骤详解1. 环境准备2. 项目功能结

SpringBoot使用ffmpeg实现视频压缩

《SpringBoot使用ffmpeg实现视频压缩》FFmpeg是一个开源的跨平台多媒体处理工具集,用于录制,转换,编辑和流式传输音频和视频,本文将使用ffmpeg实现视频压缩功能,有需要的可以参考... 目录核心功能1.格式转换2.编解码3.音视频处理4.流媒体支持5.滤镜(Filter)安装配置linu

Redis中的Lettuce使用详解

《Redis中的Lettuce使用详解》Lettuce是一个高级的、线程安全的Redis客户端,用于与Redis数据库交互,Lettuce是一个功能强大、使用方便的Redis客户端,适用于各种规模的J... 目录简介特点连接池连接池特点连接池管理连接池优势连接池配置参数监控常用监控工具通过JMX监控通过Pr

apache的commons-pool2原理与使用实践记录

《apache的commons-pool2原理与使用实践记录》ApacheCommonsPool2是一个高效的对象池化框架,通过复用昂贵资源(如数据库连接、线程、网络连接)优化系统性能,这篇文章主... 目录一、核心原理与组件二、使用步骤详解(以数据库连接池为例)三、高级配置与优化四、典型应用场景五、注意事

使用Python实现Windows系统垃圾清理

《使用Python实现Windows系统垃圾清理》Windows自带的磁盘清理工具功能有限,无法深度清理各类垃圾文件,所以本文为大家介绍了如何使用Python+PyQt5开发一个Windows系统垃圾... 目录一、开发背景与工具概述1.1 为什么需要专业清理工具1.2 工具设计理念二、工具核心功能解析2.

MySQL 添加索引5种方式示例详解(实用sql代码)

《MySQL添加索引5种方式示例详解(实用sql代码)》在MySQL数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中,下面给大家分享MySQL添加索引5种方式示例详解(实用sql代码),... 在mysql数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中。索引可以在创建表时定义,也可

Linux系统之stress-ng测压工具的使用

《Linux系统之stress-ng测压工具的使用》:本文主要介绍Linux系统之stress-ng测压工具的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、理论1.stress工具简介与安装2.语法及参数3.具体安装二、实验1.运行8 cpu, 4 fo

Java使用MethodHandle来替代反射,提高性能问题

《Java使用MethodHandle来替代反射,提高性能问题》:本文主要介绍Java使用MethodHandle来替代反射,提高性能问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录一、认识MethodHandle1、简介2、使用方式3、与反射的区别二、示例1、基本使用2、(重要)

使用C#删除Excel表格中的重复行数据的代码详解

《使用C#删除Excel表格中的重复行数据的代码详解》重复行是指在Excel表格中完全相同的多行数据,删除这些重复行至关重要,因为它们不仅会干扰数据分析,还可能导致错误的决策和结论,所以本文给大家介绍... 目录简介使用工具C# 删除Excel工作表中的重复行语法工作原理实现代码C# 删除指定Excel单元

Python实现一键PDF转Word(附完整代码及详细步骤)

《Python实现一键PDF转Word(附完整代码及详细步骤)》pdf2docx是一个基于Python的第三方库,专门用于将PDF文件转换为可编辑的Word文档,下面我们就来看看如何通过pdf2doc... 目录引言:为什么需要PDF转Word一、pdf2docx介绍1. pdf2docx 是什么2. by