专业做app下载网站有哪些,如何编写网站,团购网站模板免费下载,网站开发工作难吗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 {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;}
}这段代码是使用Java编写的实现了一个计算斐波那契数列第n项的函数。斐波那契数列定义为每个数字是前两个数字之和通常以0和1开始。这里是一个详细解析
函数签名
public int fib(int n)该函数名为fib接受一个整数参数n返回计算出的斐波那契数列的第n项。
函数逻辑 基本情况处理: if (n 2) return n;如果n小于2即n为0或1直接返回n因为斐波那契数列的前两项分别是0和1。 迭代计算斐波那契数: 初始化三个整数变量 int a 0, b 1, c 0;其中a和b用于存储当前要相加的两个斐波那契数初始化为0和1c用于存储它们的和。 接下来是一个for循环从1遍历到n-1因为a和b已经表示了第一项和第二项 for (int i 1; i n; i) {c a b;a b;b c;
}在每次循环中先计算a和b的和赋值给c然后将b的值赋予a将c的值赋予b这样a和b始终指向当前需要考虑的斐波那契数列的两项而c则保存了新的和。 返回结果: 循环结束后c中存储的就是斐波那契数列的第n项直接返回c即可。
示例
例如如果调用fib(6)函数会返回斐波那契数列的第6项计算过程如下
初始a0, b1, c0第1次循环后a1, b1, c1第2次循环后a1, b2, c3第3次循环后a2, b3, c5第4次循环后a3, b5, c8第5次循环后a5, b8, c13
因此fib(6)返回13。
方法二
//非压缩状态的版本
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];}
}这段代码是使用Java语言实现的一个计算斐波那契数列第n项的函数。斐波那契数列是一个经典的数列其中每一项都是前两项的和通常以0和1开始。下面是这段代码的详细解释
函数签名
public int fib(int n)这个函数名为fib接收一个整数n作为参数返回斐波那契数列的第n项。
函数逻辑 基本情况处理: if (n 1) return n;如果输入的n小于或等于1根据斐波那契数列的定义直接返回n自身因为fib(0)0且fib(1)1。 初始化动态规划数组: int[] dp new int[n 1];
dp[0] 0;
dp[1] 1;创建一个长度为n1的数组dp来存储斐波那契数列的值其中dp[0]0和dp[1]1对应斐波那契数列的前两项。 动态规划填充数组: for (int index 2; index n; index){dp[index] dp[index - 1] dp[index - 2];
}从索引2开始遍历到n包含n使用循环依次计算并存储斐波那契数列的每一项。每一项dp[index]的值由前两项dp[index - 1]和dp[index - 2]的和计算得出这是斐波那契数列的基本定义。 返回结果: return dp[n];在循环结束后数组dp的最后一个元素dp[n]即为斐波那契数列的第n项所以直接返回该值。
示例
比如如果调用fib(6)函数会计算并返回斐波那契数列的第6项即0, 1, 1, 2, 3, 5, 8中的8。
这种方法称为动态规划相较于递归解法它避免了重复计算提高了效率特别是在计算较大的n时更为明显。
70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
示例 1
输入n 2 输出2 解释有两种方法可以爬到楼顶。
1 阶 1 阶2 阶 示例 2
输入n 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];
}这段代码是使用Java语言实现的一种动态规划方法用于解决“爬楼梯”问题。问题描述如下假设你正在爬一个楼梯每次你可以爬1阶或者2阶。给定楼梯的总阶数n返回爬到楼顶的方法总数。
代码解析 初始化: 创建一个长度为n 1的整型数组dp用来存储爬到各个阶梯的方法数。dp[0]和dp[1]都初始化为1表示爬到第0阶有1种方法即不爬爬到第1阶也有1种方法直接爬一阶上去。 状态转移方程: 对于dp[i]其中i 2可以根据状态转移方程dp[i] dp[i - 1] dp[i - 2]来计算即爬到第i阶的方法数等于爬到第i - 1阶的方法数加上爬到第i - 2阶的方法数。这是因为到达第i阶要么是从第i - 1阶爬一阶上来要么是从第i - 2阶爬两阶上来。 返回结果: 最终dp[n]就是爬到第n阶楼梯的方法总数因此返回dp[n]作为答案。
举例说明
假设n 3即有3阶楼梯按照代码逻辑计算过程如下
dp[0] 1, dp[1] 1计算dp[2]时dp[2] dp[1] dp[0] 1 1 2表示到第2阶有2种方法11 或者 2。计算dp[3]时dp[3] dp[2] dp[1] 2 1 3表示到第3阶有3种方法111, 12, 或者 21。
因此当n 3时返回的结果是3即有3种不同的方法爬到楼顶。
方法二
// 用变量记录代替数组
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;}
}这段代码是使用Java语言实现的一个简化版的动态规划方法来解决“爬楼梯”问题。与之前使用数组记录每个阶梯的方法数不同这里仅使用了三个变量a、b和sum来减少空间复杂度达到了O(1)的空间复杂度要求而时间复杂度仍然是O(n)。下面是代码的详细解释
代码逻辑解析 基础情况处理: 如果输入的阶数n小于等于2直接返回n因为当只有1阶或2阶楼梯时方法数分别为1和2。 变量初始化: 定义三个整型变量a、b和sum其中a和b分别初始化为1和2对应爬到第一阶和第二阶楼梯的方法数。sum用来临时存储每轮循环中爬到当前阶的方法数。 循环计算: 从第三阶楼梯(i 3)开始计算直到目标阶数n。在每次循环中 计算sum a b即当前阶的方法数等于前一阶的方法数加上前两阶的方法数。更新a b把当前的b值即上一阶的方法数赋给a为下一轮计算做准备。更新b sum把刚计算出来的sum当前阶的方法数赋给b为下一轮计算做准备。 返回结果: 循环结束后变量b中存储的就是爬到n阶楼梯的方法总数直接返回b。
举例说明
假设我们要计算爬5阶楼梯的方法数过程如下
初始a 1到第1阶的方法数b 2到第2阶的方法数。第一轮计算阶数3: sum a b 1 2 3更新后a 2, b 3。第二轮计算阶数4: sum a b 2 3 5更新后a 3, b 5。第三轮计算阶数5: sum a b 3 5 8此时b即为爬到第5阶的方法数。
最终返回b 8表示有8种不同的方法可以爬到5阶楼梯的顶部。
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 {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];}
}这段Java代码是解决“最小成本爬楼梯”问题的一个实现。给定一个非负整数数组 cost其中 cost[i] 是爬到第 i 阶楼梯的成本。一旦你支付了爬到某阶楼梯的成本就可以选择不再支付直接爬到更高一层或者爬两层。该函数的目标是计算达到顶层楼梯的最低花费。这里采用的是自底向上的动态规划方法。
代码解析 初始化首先定义数组 dp 来存储到达每个楼层的最小成本数组长度为 len 1因为我们要计算到达最后一阶楼梯之上即到达顶层的成本。初始化 dp[0] 和 dp[1] 为0意味着从地面下标0或第一个台阶下标1开始爬不需要额外支付费用。 动态规划状态转移遍历从下标2到len包括len对于每个位置 i有两种方式到达一是从 i-1 阶楼梯爬上来二是从 i-2 阶楼梯爬上来。因此到达第 i 阶楼梯的最小成本可以通过比较这两种方式的成本并取最小值得到即 dp[i] min(dp[i - 1] cost[i - 1], dp[i - 2] cost[i - 2])。 返回结果遍历结束后dp[len] 存储的就是到达顶层楼梯的最小成本直接返回这个值。
示例说明
假设 cost [10, 15, 20]表示爬到第一阶楼梯成本为0根据初始化逻辑第二阶为10第三阶为15。按照上述逻辑计算
dp[2] min(dp[1] cost[1], dp[0] cost[0]) min(0 10, 0 0) 10dp[3] min(dp[2] cost[2], dp[1] cost[1]) min(10 20, 0 15) 15
因此到达顶层即第三阶楼梯之上的最小成本为15这就是函数的返回值。
方法二
// 方式二第一步支付费用
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]);}
}这段Java代码也是解决“最小成本爬楼梯”问题的一个实现但与之前的方式稍有不同。这里是假设从第一阶楼梯开始就需要支付费用然后采用动态规划的方法来求解到达顶层楼梯的最小花费。具体解析如下
代码解析 初始化首先定义一个长度与输入数组 cost 相同的数组 dp用来存储到达每个阶梯时的最小花费。初始化 dp[0] 和 dp[1] 分别为 cost[0] 和 cost[1]表示从地面到第一阶和到第二阶的花费。 动态规划状态转移从下标为2的位置开始遍历至数组末尾不包括对于每一个位置 i到达此处的最小花费等于前一阶梯的最小花费和前前一阶梯的最小花费中的较小者再加上当前位置 i 的花费。即 dp[i] min(dp[i - 1], dp[i - 2]) cost[i]。这样做是为了确保以最少的花费到达当前阶梯。 返回结果到达顶层楼梯有两种情况一种是从倒数第一阶直接上一种是从倒数第二阶上。因此返回 dp[cost.length - 1] 和 dp[cost.length - 2] 中的较小值即为最小成本。注意这里最后一步不额外计算费用因为到达倒数第二阶时已经计算了到达顶层所需的最小花费。
示例说明
如果 cost [10, 15, 20]则
dp[0] 10dp[1] 15遍历过程中dp[2] min(dp[1], dp[0]) cost[2] min(15, 10) 20 10 20 30
最后Math.min(dp[2], dp[1]) Math.min(30, 15)因此返回 15 作为最小成本。
这种方式同样高效地解决了问题但注意其假设前提与之前的方式不同是从第一阶开始就需要支付费用。
方法三
// 状态压缩使用三个变量来代替数组
class Solution {public int minCostClimbingStairs(int[] cost) {// 以下三个变量分别表示前两个台阶的最少费用、前一个的、当前的。int beforeTwoCost 0, beforeOneCost 0, currentCost 0;// 前两个台阶不需要费用就能上到因此从下标2开始因为最后一个台阶需要跨越所以需要遍历到cost.lengthfor (int i 2; i cost.length; i ) {// 此处遍历的是cost[i - 1]不会越界currentCost Math.min(beforeOneCost cost[i - 1], beforeTwoCost cost[i - 2]);beforeTwoCost beforeOneCost;beforeOneCost currentCost;}return currentCost;}
}这段Java代码是解决“最小成本爬楼梯”问题的另一种实现采用了状态压缩的方法即使用三个变量而不是数组来存储到达每个阶梯所需的最小成本。这种方式减少了空间复杂度但仍然保持了动态规划的思想。下面是详细的解析
代码解析 变量定义定义三个整型变量beforeTwoCost、beforeOneCost和currentCost分别代表到达前两个台阶、前一个台阶和当前台阶的最小成本。初始时前两个台阶和前一个台阶的最小成本都设为0因为题目中并没有明确指出从第一个台阶开始就有费用但根据逻辑推断此处默认从地面到第一个和第二个台阶是免费的或者理解为beforeTwoCost和beforeOneCost是站在第一阶和第二阶的费用自然为0。 循环遍历从i 2开始遍历至cost.length包含cost.length意味着考虑到达顶层楼梯后的状态这一步是基于从地面下标0或第一个台阶下标1出发的逻辑但因为cost数组的下标是从0开始的所以计算时访问的是cost[i - 1]和cost[i - 2]。 状态转移在每次循环中计算到达当前台阶的最小成本currentCost通过比较从上一个台阶和前一个台阶到达当前台阶的最小花费。具体来说currentCost Math.min(beforeOneCost cost[i - 1], beforeTwoCost cost[i - 2])表示当前到达的阶梯可以通过上一个阶梯或跳过一个阶梯从更早的阶梯到达选择其中成本较小的路径。 状态更新更新beforeTwoCost和beforeOneCost的值为下一次迭代做准备。即将当前的beforeOneCost赋值给beforeTwoCost将刚刚计算的currentCost赋值给beforeOneCost。 返回结果循环结束后currentCost即为到达顶层楼梯所需的最小成本直接返回。
示例说明
如果输入数组cost [10, 15, 20]则遍历过程如下
初始化beforeTwoCost 0, beforeOneCost 0第一轮计算i 2currentCost min(0 10, 0 0) 10更新后beforeTwoCost 0, beforeOneCost 10第二轮计算i 3currentCost min(10 15, 0 20) 20更新后beforeTwoCost 10, beforeOneCost 20
遍历结束currentCost 20即为最小成本因此返回20。
