当前位置: 首页 > news >正文

代码随想录27期|Python|Day38|509斐波那契|738.爬楼梯|746.746. 使用最小花费爬楼梯

 贴一下动态规划的步骤(5步),就像是之前递归一样,需要每次落实到位。

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

​​​​​509. 斐波那契

注意到n的范围是30以内,一个更快的方法是直接把这个数组先算出来,然后直接取。

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""fib_list = self.pre_print()return fib_list[n]def pre_print(self):fib_list = [0, 1, 1]for i in range(3, 31):fib_list.append(fib_list[i-2] + fib_list[i-1])return fib_list

当然可以使用递归: 

class Solution(object):def fib(self, n):""":type n: int:rtype: int"""## 递归解法if n < 2:return nelse:return self.fib(n-1) + self.fib(n-2)

70. 爬楼梯

在规定了每次只能走1或者2步的时候,本题的本质就是求解斐波那契鹅数列。

可以看到,dp[i]在第三位开始,往前看一位dp[i-1],只有一种情况(就是走1步),往前看两位dp[i-2],只有一种情况(就是走2步,因为走1步的已经算在dp[i-1]里面了)

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

则自然可以看出是斐波那契。

关于dp[0]的初始化:由于题目说是从1开始,所以0直接排除了。但是对于一般的动态规划为题(如之前的斐波那契),都需要考虑0的初始化。本题直接初始化dp[1]=1,dp[2]=2即可。

class Solution(object):def climbStairs(self, n):""":type n: int:rtype: int"""if n <= 2:return n# 初始化dp = [0] * 3dp[1] = 1dp[2] = 2  # 实际上只用到了2个位置# 推倒关系for i in range(3, n+1):  # 注意i开始和结束的值total = dp[1] + dp[2]dp[1] = dp[2]dp[2] = totalreturn dp[2]

746. 使用最小花费爬楼梯

本题关键在于如何确定dp数组和下标的含义。

1、确定dp数组和下标的含义:数组的第i个代表走到第i个所需要的最小花费;

2、初始化:由于0和1不需要花费,所以dp都是0;

3、递推:当前i个的最小花费是取决于前2个dp值和cost的值,取和的最小值。

class Solution(object):def minCostClimbingStairs(self, cost):""":type cost: List[int]:rtype: int"""dp = [0] * (len(cost)+1)dp[0], dp[1] = 0, 0for i in range(2, len(dp)):dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])return dp[-1] 

Day38完结!!!

http://www.lryc.cn/news/416795.html

相关文章:

  • windows docker容器部署前端项目
  • 科普文:微服务之全文检索ElasticSearch 集群的搭建
  • QtObject是干什么的?
  • 锐捷RCNA | 远程登录与路由技术
  • 实现Vue-tiny-diff算法
  • 正则表达式测试工具
  • Github 2024-08-02 开源项目日报 Top9
  • 重生之我 学习【数据结构之顺序表(SeqList)】
  • 前端day4-表单标签
  • vue3-print-nb 表格打印分页,第一页有空白的情况出现解决方法(两种:一种原生,一种基于element表格)
  • 搜维尔科技:借助 Xsens中的远程人体录制功能,可以在任何位置以无限量同时捕捉无限数量演员的身体动作
  • 2024/08 近期关于AI的阅读和理解[笔记]
  • SmartEDA:解锁设计新境界,从工具到灵感的飞跃之旅!
  • 解决Minizip压缩后解压时的头部错误问题
  • 数据库表水平分割和垂直分割?
  • Linux源码阅读笔记18-插入模型及删除模块操作
  • 力扣面试经典算法150题:移除元素
  • java关于前端传布尔值后端接收一直为false问题
  • 工具学习_CVE Binary Tool
  • 智观察 | 行业赛道里的AI大模型
  • linux 进程 inode 信息获取
  • 计算机网络-网络层
  • 机器学习:识别AI,GraphRAG,LoRA,线性变换,特征
  • 阿里云SMS服务C++ SDK编译及调试关键点记录
  • Flutter 正在迁移到 Swift Package Manager ,未来会弃用 CocoaPods 吗?
  • PDF——分割pdf的10个工具
  • 深入解析 Nginx 反向代理:配置、优化与故障排除
  • 深度学习入门(一):感知机与输入数据
  • kubernetes 集群组件介绍
  • Java | Leetcode Java题解之第327题区间和的个数