电子商务网站开发与建设,wordpress免费建站教程,泉州野外拓展网站建设,网站建好用电脑做服务器题目描述
斐波那契数#xff0c;通常用 F(n) 表示#xff0c;形成的序列称为斐波那契数列。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。也就是#xff1a;
F(0) 0#xff0c;F(1) 1
F(n) F(n - 1) F(n - 2)#xff0c;其中 n 1。…题目描述
斐波那契数通常用 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。解题思路
动态规划
定义状态 设 dp[i] 表示斐波那契数列的第 i 项。状态转移方程 dp[i] dp[i-1] dp[i-2]即第 i 项等于第 i-1 项和第 i-2 项的和。初始状态 dp[0] 0dp[1] 1。遍历顺序 从小到大遍历计算每一项的值。
特殊案例
如果输入 n 为 0 或 1则直接返回 n。
C#代码实现
public int Fib(int n) {// 如果N等于0或者1直接返回Nif (n 0 || n 1) {return n;}// 创建一个长度为N1的数组dpint[] dp new int[n 1];// 初始化dp数组dp[0]和dp[1]都等于0dp[0] 0;dp[1] 1;// 从2开始遍历每次循环dp[i]等于dp[i-1]和dp[i-2]的和for (int i 2; i n; i) {dp[i] dp[i - 1] dp[i - 2];}// 返回dp[n]return dp[n];
}C代码实现
int fib(int n) {// 如果N等于0或者1直接返回Nif (n 0 || n 1) {return n;}// 动态规划dp[i]表示第i个斐波那契数int* dp (int*)malloc(sizeof(int) * (n 1));// 初始化dp[0]和dp[1]dp[0] 0;dp[1] 1;// 从2开始计算斐波那契数for (int i 2; i n; i) {// 递推公式dp[i] dp[i - 1] dp[i - 2]dp[i] dp[i - 1] dp[i - 2];}// 记录结果int result dp[n];// 释放内存free(dp);return result;
}时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是斐波那契数列的项数。需要计算每一项的值。空间复杂度O(n)。使用了一个大小为 n1 的数组来保存中间结果。
