每日一题-斐波那契数列和跳台阶

斐波那契数列

题目描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列的定义：

• $ \text{fib}(x) = 1 \quad \text{(x = 1 or x = 2)} $
• $ \text{fib}(x) = \text{fib}(x-1) + \text{fib}(x-2) \quad \text{(x > 2)} $

数据范围：

$ 1 \leq n \leq 40 $

题目要求：

• 空间复杂度：$O(1)$
• 时间复杂度：$O(n)$，但是也可以使用$O(\log n)$ 的解法。

---

输入描述：

一个正整数 n。

---

输出描述：

输出斐波那契数列的第 n 项。

---

示例

示例 1：

输入：

4

输出：

3

说明：
根据斐波那契数列的定义可知，fib(1)=1，fib(2)=1，fib(3)=fib(3-1)+fib(3-2)=2，fib(4)=fib(4-1)+fib(4-2)=3，所以答案为 3。

示例 2：

输入：

1

输出：

1

示例 3：

输入：

2

输出：

1

---

解法

1. 递归解法

递归的做法是基于斐波那契数列的定义，逐步向下调用。时间复杂度是 O($2^n$)，并且会大量重复计算，所以效率较低。

int Fibonacci(int n) {if (n <= 2)return 1;else return Fibonacci(n - 1) + Fibonacci(n - 2);
}

代码解释：

• if (n <= 2): 递归的终止条件，当 n 为 1 或 2 时，返回 1。
• else return Fibonacci(n - 1) + Fibonacci(n - 2): 如果 n 大于 2，则根据斐波那契数列的定义，递归计算 fib(n-1) 和 fib(n-2)，并返回它们的和。

2. 动态规划解法（自底向上）

为了解决递归解法中重复计算的问题，我们可以使用动态规划的方式来从底到顶逐步计算每一项斐波那契数，并记录下来，避免重复计算。

int Fibonacci(int n) {if (n <= 2) return 1;int prev1 = 1, prev2 = 1, current;for (int i = 3; i <= n; ++i) {current = prev1 + prev2;prev2 = prev1;prev1 = current;}return current;
}

代码解释：

• if (n <= 2) return 1;: 若 n 为 1 或 2，直接返回 1。
• int prev1 = 1, prev2 = 1, current;: 使用三个变量 prev1、prev2 和 current 来保存斐波那契数列的前两项和当前项。
• for (int i = 3; i <= n; ++i): 从第三项开始循环计算，逐步得到下一个斐波那契数。
• current = prev1 + prev2;: 当前项是前两项的和。
• prev2 = prev1; prev1 = current;: 更新 prev1 和 prev2 为当前项和前两项。

---

跳台阶问题

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：
1 ≤ n ≤ 40

要求：
时间复杂度：O(n)
空间复杂度：O(1)

---

示例

示例1

输入：
2
返回值：
2
说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2。

示例2

输入：
7
返回值：
21

---

解题思路

方法一：递归

递归的思路是，青蛙跳上第n级台阶的跳法等于跳上第n-1级台阶的跳法加上跳上第n-2级台阶的跳法。即：

f(n) = f(n-1) + f(n-2)

代码实现：

#include <stdio.h>int jumpFloor(int number) {if (number == 0 || number == 1) {return 1;} else {return jumpFloor(number - 1) + jumpFloor(number - 2);}
}

时间复杂度：
O(2^n)，因为每次递归调用会产生两个新的递归调用，导致指数级的时间复杂度。

空间复杂度：
O(n)，递归调用栈的深度为n。

方法二：动态规划

为了优化递归方法的时间复杂度，我们可以使用动态规划来避免重复计算。通过保存中间结果，可以将时间复杂度降低到O(n)。

代码实现：

#include <stdio.h>int jumpFloor(int number) {int a = 1;int b = 1;int c = 1;if (number == 0 || number == 1) {return 1;}for (int i = 1; i < number; i++) {a = b;b = c;c = a + b;}return c;
}

时间复杂度：
O(n)，只需要遍历一次即可计算出结果。

空间复杂度：
O(1)，只使用了常数个额外空间。

---

总结

• 递归方法 简单直观，但时间复杂度较高，适合小规模问题。
• 动态规划方法 通过保存中间结果，大大降低了时间复杂度，适合大规模问题。

最小花费爬楼梯

题目描述

给定一个整数数组 cost，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用，下标从 0 开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：

• 数组长度满足 (1 \leq n \leq 10^5)。
• 数组中的值满足 (1 \leq \text{cost}_i \leq 10^4)。

---

示例

示例 1

输入：
[2, 5, 20]
返回值：
5
说明：
你将从下标为 1 的台阶开始，支付 5，向上爬两个台阶，到达楼梯顶部。总花费为 5。

示例 2

输入：
[1, 100, 1, 1, 1, 90, 1, 1, 80, 1]
返回值：
6
说明：
你将从下标为 0 的台阶开始：

1. 支付 1，向上爬两个台阶，到达下标为 2 的台阶。
2. 支付 1，向上爬两个台阶，到达下标为 4 的台阶。
3. 支付 1，向上爬两个台阶，到达下标为 6 的台阶。
4. 支付 1，向上爬一个台阶，到达下标为 7 的台阶。
5. 支付 1，向上爬两个台阶，到达下标为 9 的台阶。
6. 支付 1，向上爬一个台阶，到达楼梯顶部。
   总花费为 6。

---

解题思路

动态规划

这是一个典型的动态规划问题。我们可以通过以下步骤解决：

1. 定义状态：

   • 设 dp[i] 表示到达第 i 级台阶的最低花费。

2. 状态转移方程：

   • 对于第 i 级台阶，可以从第 i-1 级或第 i-2 级台阶爬上来。
   • 因此，状态转移方程为：
     [
     dp[i] = \min(dp[i-1] + \text{cost}[i-1], dp[i-2] + \text{cost}[i-2])
     ]

3. 初始条件：

   • dp[0] = 0：到达第 0 级台阶不需要花费。
   • dp[1] = 0：到达第 1 级台阶不需要花费。

4. 目标：

   • 计算 dp[n]，其中 n 是楼梯的总台阶数。

---

代码实现

C 语言实现

#include <stdio.h>
#include <stdlib.h>int minCostClimbingStairs(int* cost, int costLen) {// 动态规划数组int* dp = (int*)malloc((costLen + 1) * sizeof(int));dp[0] = 0; // 到达第 0 级的成本dp[1] = 0; // 到达第 1 级的成本// 填充 dp 数组for (int i = 2; i <= costLen; i++) {int temp1 = dp[i - 1] + cost[i - 1]; // 从第 i-1 级爬上来int temp2 = dp[i - 2] + cost[i - 2]; // 从第 i-2 级爬上来dp[i] = temp1 < temp2 ? temp1 : temp2; // 取最小值}int result = dp[costLen]; // 最终结果free(dp); // 释放动态规划数组return result;
}

---

代码解析

1. 动态规划数组：

   • 使用 dp 数组存储到达每一级台阶的最低花费。
   • dp[0] 和 dp[1] 初始化为 0，因为从第 0 级或第 1 级开始不需要花费。

2. 状态转移：

   • 对于每一级台阶 i，计算从 i-1 级和 i-2 级爬上来的花费，取最小值。

3. 结果：

   • dp[costLen] 表示到达楼梯顶部的最低花费。

4. 内存管理：

   • 使用 malloc 动态分配内存，使用 free 释放内存。

---

复杂度分析

• 时间复杂度：(O(n))，其中 (n) 是楼梯的台阶数。需要遍历一次 cost 数组。
• 空间复杂度：(O(n))，用于存储动态规划数组 dp。