网站开发包含上线吗,网站加载慢,国际新闻最新消息今天新闻大事件视频,宁波企业网站建设公司题目
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;其…题目
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 {public int fib(int n) {if (n 2) return n;int a 0, b 1, c 0;for (int i 1; i n; i) {c a b;a b;b c;}return c;}
}//非压缩状态的版本
class Solution {public int fib(int n) {if (n 1) return n; int[] dp new int[n 1];dp[0] 0;dp[1] 1;for (int index 2; index n; index){dp[index] dp[index - 1] dp[index - 2];}return dp[n];}
}70、爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
示例 1
输入 2 输出 2 解释 有两种方法可以爬到楼顶。 1 阶 1 阶 2 阶 示例 2
输入 3 输出 3 解释 有三种方法可以爬到楼顶。 1 阶 1 阶 1 阶 1 阶 2 阶 2 阶 1 阶
// 常规方式
public int climbStairs(int n) {int[] dp new int[n 1];dp[0] 1;dp[1] 1;for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}return dp[n];
}// 用变量记录代替数组
class Solution {public int climbStairs(int n) {if(n 2) return n;int a 1, b 2, sum 0;for(int i 3; i n; i){sum a b; // f(i - 1) f(i - 2)a b; // 记录f(i - 1)即下一轮的f(i - 2)b sum; // 记录f(i)即下一轮的f(i - 1)}return b;}
}746、使用最小花费爬楼梯
数组的每个下标作为一个阶梯第 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 {public int minCostClimbingStairs(int[] cost) {int len cost.length;int[] dp new int[len 1];// 从下标为 0 或下标为 1 的台阶开始因此支付费用为0dp[0] 0;dp[1] 0;// 计算到达每一层台阶的最小费用for (int i 2; i len; i) {dp[i] Math.min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2]);}return dp[len];}
}// 方式二第一步支付费用
class Solution {public int minCostClimbingStairs(int[] cost) {int[] dp new int[cost.length];dp[0] cost[0];dp[1] cost[1];for (int i 2; i cost.length; i) {dp[i] Math.min(dp[i - 1], dp[i - 2]) cost[i];}//最后一步如果是由倒数第二步爬则最后一步的体力花费可以不用算return Math.min(dp[cost.length - 1], dp[cost.length - 2]);}
}
