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
【算法设计思想】
本题可以看作是入门动态规划的经典第一题。
- 定义状态:
- 状态是指问题的一个特定阶段的状态。对于斐波那契数列,状态可以定义为
dp[i]
,表示斐波那契数列的第i
个数字。
- 状态是指问题的一个特定阶段的状态。对于斐波那契数列,状态可以定义为
- 确定状态转移方程:
- 状态转移方程描述了如何从一个或多个先前的状态转移到当前状态。对于斐波那契数列,状态转移方程为
dp[i] = dp[i - 1] + dp[i - 2]
,表示第i
个斐波那契数等于前两个斐波那契数之和。
- 状态转移方程描述了如何从一个或多个先前的状态转移到当前状态。对于斐波那契数列,状态转移方程为
- 初始化:
- 初始化一些基本情况,以便开始递推计算。对于斐波那契数列,初始化
dp[0] = 0
和dp[1] = 1
。
- 初始化一些基本情况,以便开始递推计算。对于斐波那契数列,初始化
- 确定计算顺序:
- 确定状态的计算顺序,通常是从已知状态逐步推导到最终状态。对于斐波那契数列,计算顺序是从
dp[0]
和dp[1]
开始,逐步计算到dp[n]
。
- 确定状态的计算顺序,通常是从已知状态逐步推导到最终状态。对于斐波那契数列,计算顺序是从
- 返回结果:
- 最后返回所需的最终结果。对于斐波那契数列,返回
dp[n]
。
- 最后返回所需的最终结果。对于斐波那契数列,返回
【算法描述】
C++:
class Solution {
public:
// 计算斐波那契数列的第n个数字
int fib(int n) {
// 如果n为0,直接返回0,因为斐波那契数列的第一个数字是0
if (n == 0)
return 0;
// 创建一个数组来存储斐波那契数列中的前n+1个数字
int dp[n + 1];
// 初始化斐波那契数列的前两个数字
dp[0] = 0; // 第0个数字是0
dp[1] = 1; // 第1个数字是1
// 使用循环计算从第2个到第n个斐波那契数
for (int i = 2; i <= n; i++) {
// 每个斐波那契数等于它前面两个斐波那契数之和
dp[i] = dp[i - 1] + dp[i - 2];
}
// 返回计算得到的第n个斐波那契数
return dp[n];
}
};
Java:
class Solution {
// 定义一个公共方法fib,用于计算斐波那契数列的第n个数字
public int fib(int n) {
// 如果n为0,根据斐波那契数列的定义,返回0
if (n == 0) return 0;
// 创建一个长度为n+1的数组dp,用于存储斐波那契数列中从第0个到第n个数字
int[] dp = new int[n + 1];
// 初始化斐波那契数列的前两个值
dp[0] = 0; // 根据定义,斐波那契数列的第0个数字是0
dp[1] = 1; // 根据定义,斐波那契数列的第1个数字是1
// 从第2个数字开始,利用动态规划的思想计算每个斐波那契数
for (int i = 2; i <= n; i++) {
// 当前位置的斐波那契数等于前两个斐波那契数之和
dp[i] = dp[i - 1] + dp[i - 2];
}
// 返回斐波那契数列的第n个数字
return dp[n];
}
}
Python:
class Solution:
def fib(self, n: int) -> int:
# 如果n为0,根据斐波那契数列的定义,返回0
if n == 0:
return 0
# 初始化dp列表,使用列表推导式来创建一个包含n+1个元素的列表,所有元素初始值都为0
dp = [0] * (n + 1)
# 根据斐波那契数列的定义,设置dp[0]和dp[1]的值
dp[0] = 0
dp[1] = 1
# 从第2个数字开始,使用动态规划计算斐波那契数列中的每一个数字
for i in range(2, n + 1):
# 当前位置的斐波那契数等于前两个斐波那契数之和
dp[i] = dp[i - 1] + dp[i - 2]
# 返回斐波那契数列的第n个数字
return dp[n]
C:
int fib(int n) {
// 如果n为0,根据斐波那契数列的定义,返回0
if(n == 0) return 0;
// 创建一个大小为n+1的数组dp,用于存储斐波那契数列中从第0个到第n个数字
int dp[n + 1];
// 初始化斐波那契数列的前两个值
dp[0] = 0; // 第0个数字是0
dp[1] = 1; // 第1个数字是1
// 从第2个数字开始,使用动态规划计算斐波那契数列中的每一个数字
for(int i = 2; i <= n; i++) {
// 当前位置的斐波那契数等于前两个斐波那契数之和
dp[i] = dp[i - 1] + dp[i - 2];
}
// 返回斐波那契数列的第n个数字
return dp[n];
}
标签:契数,数列,int,斐波,509,那契,dp,数字
From: https://www.cnblogs.com/zeta186012/p/18496307