LeetCode 509、 斐波那契数
LeetCode 509、 斐波那契数
一、题目描述
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(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
提示：
0 <= n <= 30
二、题目解析
三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 斐波那契数（LeetCode 509）：https://leetcode.cn/problems/fibonacci-number/
class Solution {
int times1;
public int fib(int N) {
times1 = 0;
int result = myFib1(N);
return result ;
}
private int myFib1( int N){
times1++;
if ( N == 0 ) return 0 ;
if ( N == 1 ) return 1 ;
return myFib1( N - 1 ) + myFib1( N - 2);
}
}
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 斐波那契数（LeetCode 509）：https://leetcode.cn/problems/fibonacci-number/
class Solution {
int times1;
int[] memo;
public int fib(int N) {
times1 = 0;
memo = new int[ N + 1 ];
Arrays.fill(memo, -1);
int result = myFib2(N);
System.out.println("myFib2 调用的次数为 ： " + times1 );
return result ;
}
// 记忆化搜索
// 在递归的基础上增加了一个记忆的功能，依旧是自上向下的解决问题
// 相当于数组从后向前挖坑，挖到最前面在开始填坑
private int myFib2( int N){
times1++;
if ( N == 0 ) return 0 ;
if ( N == 1 ) return 1 ;
if ( memo[N] == -1) {
memo[N] = myFib2( N - 1 ) + myFib2( N - 2);
}
return memo[N];
}
}
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 添加微信 278166530 获取最新课程
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 斐波那契数（LeetCode 509）：https://leetcode.cn/problems/fibonacci-number/
class Solution {
int times1;
int[] memo;
public int fib(int N) {
times1 = 0;
memo = new int[ N + 1 ];
Arrays.fill(memo, -1);
int result = myFib3(N);
System.out.println("myFib3 调用的次数为 ： " + times1 );
return result ;
}
// 动态规划：自下向上的解决问题
// 相当于结果数组从前往后进行填充，一个萝卜一个坑
private int myFib3( int N){
if ( N < 2) return N;
// 1、确定 dp 数组的含义
// 即 dp[n] 表示当 n 时是xxxx
int[] dp = new int[ N + 1];
// 3、确定 dp 初始状态
// 初始化默认值、前面几个状态的值
Arrays.fill(dp,-1);
dp[0] = 0;
dp[1] = 1;
for(int i = 2 ; i <= N ; i++){
// 2、寻找 dp 数组元素之间的联系
// 即 dp[i] 的状态可以怎么样通过前面的状态获取到
dp[i] = dp[i-1] + dp[i-2];
}
return dp[N];
}
}class Solution:
def __init__(self):
self.times1 = 0
def fib(self, N):
self.times1 = 0
result = self.myFib1(N)
print(self.times1)
return result
def myFib1(self, N):
self.times1 += 1
if N == 0:
return 0
if N == 1:
return 1
return self.myFib1(N - 1) + self.myFib1(N - 2)
# 记忆化搜索
class Solution:
def __init__(self):
self.times1 = 0
self.memo = None
def fib(self, N):
self.times1 = 0
self.memo = [-1] * (N + 1)
result = self.myFib2(N)
print("myFib2 调用的次数为: ", self.times1)
return result
def myFib2(self, N):
self.times1 += 1
if N == 0:
return 0
if N == 1:
return 1
if self.memo[N] == -1:
self.memo[N] = self.myFib2(N - 1) + self.myFib2(N - 2)
return self.memo[N]
# 动态规划
class Solution:
def __init__(self):
self.times1 = 0
self.memo = None
def fib(self, N):
self.times1 = 0
self.memo = [-1] * (N + 1)
result = self.myFib3(N)
print("myFib3 调用的次数为: ", self.times1)
return result
def myFib3(self, N):
if N < 2:
return N
dp = [-1] * (N + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, N + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[N]class Solution {
public:
int times1; // 用于统计递归调用的次数
// 构造函数
Solution() {
times1 = 0;
}
// 计算斐波那契数的函数
int fib(int N) {
times1 = 0; // 重置递归调用计数
int result = myFib1(N);
std::cout << times1 << std::endl; // 输出递归调用的次数
return result;
}
private:
// 递归计算斐波那契数的辅助函数
int myFib1(int N) {
times1++; // 每调用一次递归函数，计数加1
// 斐波那契数的基本情况：N为0时返回0
if (N == 0) {
return 0;
}
// 斐波那契数的基本情况：N为1时返回1
if (N == 1) {
return 1;
}
// 递归计算斐波那契数
return myFib1(N - 1) + myFib1(N - 2);
}
};
class Solution {
public:
int times1; // 统计 myFib2 调用的次数
std::vector<int> memo; // 用于记忆化搜索的数组
// 构造函数
Solution() {
times1 = 0;
}
// 主函数，计算斐波那契数
int fib(int N) {
times1 = 0; // 重置调用计数
memo = std::vector<int>(N + 1, -1); // 初始化 memo 数组为 -1
int result = myFib2(N);
std::cout << "myFib2 调用的次数为: " << times1 << std::endl;
return result;
}
private:
// 记忆化搜索的递归函数
int myFib2(int N) {
times1++; // 每次调用递归函数，计数加1
// 基本情况：当 N 为 0 时返回 0
if (N == 0) {
return 0;
}
// 基本情况：当 N 为 1 时返回 1
if (N == 1) {
return 1;
}
// 如果 memo[N] 还没有被计算过
if (memo[N] == -1) {
// 计算并存储到 memo[N] 中
memo[N] = myFib2(N - 1) + myFib2(N - 2);
}
// 返回 memo[N] 的值
return memo[N];
}
};
class Solution {
public:
int times1; // 记录 myFib3 调用的次数
// 构造函数
Solution() {
times1 = 0;
}
// 主函数，计算斐波那契数
int fib(int N) {
times1 = 0; // 重置调用计数
std::vector<int> memo(N + 1, -1); // 初始化 memo 数组
int result = myFib3(N);
std::cout << "myFib3 调用的次数为: " << times1 << std::endl;
return result;
}
private:
// 动态规划实现斐波那契数
int myFib3(int N) {
if (N < 2) {
return N; // 基本情况：当 N 小于 2 时，直接返回 N
}
std::vector<int> dp(N + 1, -1); // 初始化 dp 数组
dp[0] = 0; // dp[0] 表示斐波那契数列的第一个数
dp[1] = 1; // dp[1] 表示斐波那契数列的第二个数
// 使用动态规划计算斐波那契数列的值
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 状态转移方程
}
return dp[N]; // 返回第 N 个斐波那契数
}
};