如何策划网站,设计网站建设公司,赣州市微程网络科技有限公司,云主机 网站 多个二级域名 seo优化动态规划 - 1137.第N个泰波那契数(C#和C实现)
题目描述
泰波那契序列 Tn 定义如下#xff1a;
T0 0, T1 1, T2 1#xff0c;且在 n 0 的条件下 Tn3 Tn Tn1 Tn2。给你整数 n#xff0c;请返回第 n 个泰波那契数 Tn 的值。
示例 1:
输入#xff1a;n 4
输出…动态规划 - 1137.第N个泰波那契数(C#和C实现)
题目描述
泰波那契序列 Tn 定义如下
T0 0, T1 1, T2 1且在 n 0 的条件下 Tn3 Tn Tn1 Tn2。给你整数 n请返回第 n 个泰波那契数 Tn 的值。
示例 1:
输入n 4
输出4
解释
T_3 0 1 1 2
T_4 1 1 2 4示例 2:
输入n 25
输出1389537提示
0 n 37答案保证是一个 32 位整数即 0 answer 2^31 - 1。
解题思路
动态规划
定义状态 设 dp[i] 表示泰波那契数列的第 i 项。状态转移方程 dp[i] dp[i-3] dp[i-2] dp[i-1]即第 i 项等于第 i-3、i-2 和 i-1 项的和。初始状态 dp[0] 0dp[1] 1dp[2] 1。遍历顺序 从小到大遍历计算每一项的值。
特殊案例
如果输入 n 为 0、1 或 2则直接返回 n。
C#代码实现
public int Tribonacci(int n) {if (n 0) {return 0;}// 如果n等于1或者2返回1if (n 1 || n 2) {return 1;}// 创建一个长度为n1的数组dpint[] dp new int[n 1];// dp[0]初始化为0dp[0] 0;// dp[1]初始化为1dp[1] 1;// dp[2]初始化为1dp[2] 1;// 从3开始到n结束for (int i 3; i n; i) {// dp[i]等于dp[i - 3] dp[i - 2] dp[i - 1]dp[i] dp[i - 3] dp[i - 2] dp[i - 1];}// 返回dp[n]return dp[n];
}C代码实现
int tribonacci(int n) {// 如果n等于0返回0if (n 0) {return 0;}// 如果n等于1或者2返回1if (n 1 || n 2) {return 1;}// 定义一个数组长度为n1int* dp (int*)malloc(sizeof(int) * (n 1));// 初始化数组dp[0] 0dp[1] 1dp[2] 1dp[0] 0;dp[1] 1;dp[2] 1;// 从3开始到n结束for (int i 3; i n; i) {// 状态转移方程dp[i] dp[i - 3] dp[i - 2] dp[i - 1]dp[i] dp[i - 3] dp[i - 2] dp[i - 1];}// 记录结果int result dp[n];// 释放内存free(dp);// 返回结果return result;
}时间复杂度和空间复杂度
时间复杂度O(n)其中 n 是泰波那契数列的项数。需要计算每一项的值。空间复杂度O(n)。使用了一个大小为 n1 的数组来保存中间结果。
参与点评
读者朋友们,如果您在阅读过程中,对文章的质量、易理解性有任何建议,欢迎在评论区指出,我会认真改进。
