建网站的公司价格,网站推广服务好公司排名,分类网站建设方案,网站导航html今日任务#xff1a; 1#xff09;509. 斐波那契数 2#xff09;70. 爬楼梯 3#xff09;746.使用最小花费爬楼梯 509. 斐波那契数
题目链接#xff1a;509. 斐波那契数 - 力扣#xff08;LeetCode#xff09; 斐波那契数#xff0c;通常用 F(n) 表示#xff0c;形成… 今日任务 1509. 斐波那契数 270. 爬楼梯 3746.使用最小花费爬楼梯 509. 斐波那契数
题目链接509. 斐波那契数 - 力扣LeetCode 斐波那契数通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(1) 1 F(n) F(n - 1) F(n - 2)其中 n 1 给你n 请计算 F(n) 。示例 1
输入2
输出1
解释F(2) F(1) F(0) 1 0 1示例 2
输入3
输出2
解释F(3) F(2) F(1) 1 1 2示例 3
输入4
输出3
解释F(4) F(3) F(2) 2 1 3提示
0 n 30 文章讲解代码随想录 (programmercarl.com)
视频讲解手把手带你入门动态规划 | LeetCode509.斐波那契数哔哩哔哩bilibili
思路 首先定义一个列表 f 来存储斐波那契数列的值初始包含前两项 [0, 1]。如果 n 小于等于 1则直接返回列表中对应位置的值。否则使用循环从 2 开始遍历到 n依次计算每一项的值并添加到列表 f 中。最后返回列表中索引为 n 的值即为斐波那契数列的第 n 项 class Solution:def fib(self, n: int) - int:# 初始化斐波那契数列的前两项f [0, 1]# 如果 n 小于等于 1则直接返回对应位置的值if n 1:return f[n]# 使用循环计算斐波那契数列的第 n 项for x in range(2, n 1):# 计算第 x 项的值并添加到列表中f.append(f[x - 1] f[x - 2])# 返回斐波那契数列的第 n 项return f[n]
这种比较好理解立马能想到这里面可以优化的部分在空间复杂度上面代码空间复杂度O(n)
我们可以定义一个长度为3的列表反复更新这三个数即可。空间复杂度O(3)
也可以定义3个变量反复更新3个变量。空间复杂度O(1)
class Solution:# 空间复杂度O(3)def fib(self, n: int) - int:if n 1:return ndp [0, 1]for i in range(2, n 1):total dp[0] dp[1]dp[0] dp[1]dp[1] totalreturn dp[1]# 空间复杂度O(1)def fib(self, n: int) - int:if n 1:return nprev1, prev2 0, 1for _ in range(2, n 1):curr prev1 prev2prev1, prev2 prev2, currreturn prev2
70. 爬楼梯
题目链接70. 爬楼梯 - 力扣LeetCode 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。示例 1
输入 2
输出 2
解释 有两种方法可以爬到楼顶。
1 阶 1 阶
2 阶示例 2
输入 3
输出 3
解释 有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶
1 阶 2 阶
2 阶 1 阶 文章讲解代码随想录 (programmercarl.com)
视频讲解带你学透动态规划-爬楼梯对应力扣70.爬楼梯| 动态规划经典入门题目哔哩哔哩bilibili
思路 爬到第一层楼梯有一种方法爬到二层楼梯有两种方法。 那么第一层楼梯再跨两步就到第三层 第二层楼梯再跨一步就到第三层。 所以到第三层楼梯的状态可以由第二层楼梯 和 到第一层楼梯状态推导出来那么就可以想到动态规划了。 首先定义一个列表 f 来存储爬楼梯的方法数初始包含前三项 [0, 1, 2]。其中 f[0] 为占位符不参与计算。如果 n 小于 3则直接返回列表中对应位置的值。否则使用循环从 3 开始遍历到 n依次计算每一项的值并添加到列表 f 中。每一项的值都等于前两项和前一项的和因为可以选择爬一阶或者爬两阶台阶。最后返回列表中索引为 n 的值即为爬楼梯的方法数。 class Solution:def climbStairs(self, n: int) - int:f [0,1,2]if n 3:return f[n]for x in range(3,n1):f.append(f[x-1]f[x-2])return f[n]# 空间复杂度为O(3)版本def climbStairs(self, n: int) - int:if n 1:return nf [0] * 3f[1] 1f[2] 2for i in range(3, n 1):total f[1] f[2]f[1] f[2]f[2] totalreturn f[2]# 空间复杂度为O(1)版本def climbStairs2(self, n: int) - int:if n 1:return nprev1 1prev2 2for i in range(3, n 1):total prev1 prev2prev1 prev2prev2 totalreturn prev2 746.使用最小花费爬楼梯
题目链接746. 使用最小花费爬楼梯 - 力扣LeetCode 给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
请你找出达到楼层顶部的最低花费。在开始时你可以选择从下标为 0 或 1 的元素作为初始阶梯。示例 1
输入cost [10, 15, 20]
输出15
解释最低花费是从 cost[1] 开始然后走两步即可到阶梯顶一共花费 15 。示例 2
输入cost [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出6
解释最低花费方式是从 cost[0] 开始逐个经过那些 1 跳过 cost[3] 一共花费 6 。提示
cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据范围为 [0, 999] 文章讲解代码随想录 (programmercarl.com)
视频讲解动态规划开更了| LeetCode746. 使用最小花费爬楼梯哔哩哔哩bilibili
思路 用数组展示如下 class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:# 如果台阶数小于2则不需要花费if len(cost) 2:return 0# 初始化到达前两个台阶的最低花费cost1 0cost2 0# 将顶部的台阶花费添加到列表中cost.append(0)# print(f初始化cost1{cost1},cost2{cost2})# 从第三个台阶开始计算最低花费for i in range(2, len(cost)):# 计算到达当前台阶的最低花费cost_total min(cost1 cost[i - 2], cost2 cost[i - 1])# 更新前两个台阶的最低花费cost1 cost2cost2 cost_total# print(fi{i},cost1{cost1},cost2{cost2}cost_total{cost_total})# 返回到达顶部的最低花费return cost2
