台州网站建设公司哪家好,公司网站推广执行方案,郑州门户网站建设,企业网站整站509. 斐波那契数
斐波那契数#xff0c;通常用 F(n) 表示#xff0c;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a; F(0) 0#xff0c;F(1) 1 F(n) F(n - 1) F(n - 2)#xff0c;其中 n …509. 斐波那契数
斐波那契数通常用 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
动态规划版本一
class Solution:def fib(self, n: int) - int:# 排除 Corner Caseif n 0:return 0# 创建 dp table dp [0] * (n 1)# 初始化 dp 数组dp[0] 0dp[1] 1# 遍历顺序: 由前向后。因为后面要用到前面的状态for i in range(2, n 1):# 确定递归公式/状态转移公式dp[i] dp[i - 1] dp[i - 2]# 返回答案return dp[n]动态规划版本二
class Solution: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]动态规划版本三
class Solution: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递归版本一
class Solution:def fib(self, n: int) - int:if n 2:return nreturn self.fib(n - 1) self.fib(n - 2)70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
示例 1
输入 2 输出 2 解释 有两种方法可以爬到楼顶。 1 阶 1 阶 2 阶 示例 2
输入 3 输出 3 解释 有三种方法可以爬到楼顶。 1 阶 1 阶 1 阶 1 阶 2 阶 2 阶 1 阶
动态规划版本一
空间复杂度为O(n)版本
class Solution:def climbStairs(self, n: int) - int:if n 1:return ndp [0] * (n 1)dp[1] 1dp[2] 2for i in range(3, n 1):dp[i] dp[i - 1] dp[i - 2]return dp[n]动态规划版本二
空间复杂度为O(3)版本
class Solution:def climbStairs(self, n: int) - int:if n 1:return ndp [0] * 3dp[1] 1dp[2] 2for i in range(3, n 1):total dp[1] dp[2]dp[1] dp[2]dp[2] totalreturn dp[2]动态规划版本三
空间复杂度为O(1)版本
class Solution:def climbStairs(self, n: int) - int:if n 1:return nprev1 1prev2 2for i in range(3, n 1):total prev1 prev2prev1 prev2prev2 totalreturn prev2746. 使用最小花费爬楼梯
旧题目描述
数组的每个下标作为一个阶梯第 i 个阶梯对应着一个非负数的体力花费值 cost[i]下标从 0 开始。
每当你爬上一个阶梯你都要花费对应的体力值一旦支付了相应的体力值你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时你可以选择从下标为 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] 。
动态规划版本一
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:dp [0] * (len(cost) 1)dp[0] 0 # 初始值表示从起点开始不需要花费体力dp[1] 0 # 初始值表示经过第一步不需要花费体力for i in range(2, len(cost) 1):# 在第i步可以选择从前一步i-1花费体力到达当前步或者从前两步i-2花费体力到达当前步# 选择其中花费体力较小的路径加上当前步的花费更新dp数组dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])return dp[len(cost)] # 返回到达楼顶的最小花费动态规划版本二
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:dp0 0 # 初始值表示从起点开始不需要花费体力dp1 0 # 初始值表示经过第一步不需要花费体力for i in range(2, len(cost) 1):# 在第i步可以选择从前一步i-1花费体力到达当前步或者从前两步i-2花费体力到达当前步# 选择其中花费体力较小的路径加上当前步的花费得到当前步的最小花费dpi min(dp1 cost[i - 1], dp0 cost[i - 2])dp0 dp1 # 更新dp0为前一步的值即上一次循环中的dp1dp1 dpi # 更新dp1为当前步的最小花费return dp1 # 返回到达楼顶的最小花费动态规划版本三
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:dp [0] * len(cost)dp[0] cost[0] # 第一步有花费dp[1] cost[1]for i in range(2, len(cost)):dp[i] min(dp[i - 1], dp[i - 2]) cost[i]# 注意最后一步可以理解为不用花费所以取倒数第一步第二步的最少值return min(dp[-1], dp[-2])动态规划版本四
class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:n len(cost)prev_1 cost[0] # 前一步的最小花费prev_2 cost[1] # 前两步的最小花费for i in range(2, n):current min(prev_1, prev_2) cost[i] # 当前位置的最小花费prev_1, prev_2 prev_2, current # 更新前一步和前两步的最小花费return min(prev_1, prev_2) # 最后一步可以理解为不用花费取倒数第一步和第二步的最少值
