优速网站建设,服务商,建设行业门户网站,免费虚拟云主机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
class Solution {public int fib(int n) {if(n 2) return n;int[] dp new int[n 1];dp[0] 0; dp[1] 1;for(int i 2; i dp.length; i){dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
}
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶
class Solution {public int climbStairs(int n) {if(n 1) return n;//初始化dp数组int[] dp new int[n];dp[0] 1;dp[1] 2;//递推公式for(int i 2; i dp.length; i){dp[i] dp[i - 1] dp[i - 2];}return dp[n-1];}
}
746. 使用最小花费爬楼梯
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例 1
输入cost [10,15,20]
输出15
解释你将从下标为 1 的台阶开始。
- 支付 15 向上爬两个台阶到达楼梯顶部。
总花费为 15 。
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 dp.length; i){dp[i] Math.min(dp[i-1] cost[i-1], dp[i-2] cost[i-2]);}return dp[dp.length - 1];}
}
