吉林网站网站建设,公司网站建设意见征集,全国企业工商信息查询系统,郑州营销网站托管509. 斐波那契数
斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1
F(n) F(n - 1) F(n - 2)#xff0c;其中 …509. 斐波那契数
斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是
F(0) 0F(1) 1
F(n) F(n - 1) F(n - 2)其中 n 1给定 n 请计算 F(n) 。 示例 1
输入n 2
输出1
解释F(2) F(1) F(0) 1 0 1示例 2
输入n 3
输出2
解释F(3) F(2) F(1) 1 1 2示例 3
输入n 4
输出3
解释F(4) F(3) F(2) 2 1 3 class Solution:def fib(self, n: int) - int:if n0:return 0#创建dp数组dp[0]*(n1)#初始化dp数组dp[0]0dp[1]1#确定遍历从前到后因为要使用前面的状态for i in range(2,n1):# 确定递归公式/状态转移公式dp[i]dp[i-1]dp[i-2]return dp[n]
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢 示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
示例 2
输入n 3
输出3
解释有三种方法可以爬到楼顶。
1. 1 阶 1 阶 1 阶
2. 1 阶 2 阶
3. 2 阶 1 阶 class Solution:def climbStairs(self, n: int) - int:if n1:return 1dp[0]*(n1)dp[1]1dp[2]2for i in range(3,n1):dp[i]dp[i-1]dp[i-2] #dp[i]包含dp[i-1]和dp[i-2]的两种情况return dp[n]
746. 使用最小花费爬楼梯
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。 示例 1
输入cost [10,15,20]
输出15
解释你将从下标为 1 的台阶开始。
- 支付 15 向上爬两个台阶到达楼梯顶部。
总花费为 15 。示例 2
输入cost [1,100,1,1,1,100,1,1,100,1]
输出6
解释你将从下标为 0 的台阶开始。
- 支付 1 向上爬两个台阶到达下标为 2 的台阶。
- 支付 1 向上爬两个台阶到达下标为 4 的台阶。
- 支付 1 向上爬两个台阶到达下标为 6 的台阶。
- 支付 1 向上爬一个台阶到达下标为 7 的台阶。
- 支付 1 向上爬两个台阶到达下标为 9 的台阶。
- 支付 1 向上爬一个台阶到达楼梯顶部。
总花费为 6 。class Solution:def minCostClimbingStairs(self, cost: List[int]) - int:dp[0]*(len(cost)1)dp[0]0dp[1]0for i in range(2,len(cost)1):dp[i]min(cost[i-1]dp[i-1],cost[i-2]dp[i-2])return dp[-1]
