LeetCode——1137. 第 N 个泰波那契数(Java)
2021/8/8 14:06:24
本文主要是介绍LeetCode——1137. 第 N 个泰波那契数(Java),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
题干: 泰波那契序列 Tn 定义如下: T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n,请返回第 n 个泰波那契数 Tn 的值。 示例 1: 输入:n = 4 输出:4 解释: T_3 = 0 + 1 + 1 = 2 T_4 = 1 + 1 + 2 = 4 示例 2: 输入:n = 25 输出:1389537
题解思路
返回泰波那契序列的第n个数,一看这个函数就难免不让我觉得这时斐波那契数列的哥哥 首先我们难免想到的是递归实现,当然结果也是可以预料到的,超时 所以我们这里就不得不采用动态规划的思想,每次保存前三个数字的值,而不需要每次递归计算
正确代码
// 递归超时 public int tribonacci01(int n) { if (n == 0) return 0; else if (n == 1) return 1; else if (n == 2) return 1; else return tribonacci01(n - 1) + tribonacci01(n - 2) + tribonacci01(n - 3); } //dp public int tribonacci02(int n) { if (n == 0) return 0; if (n <= 2) return 1; int T0 = 0, T1 = 0, T2 = 1, ans = 1; for (int i = 3; i <= n; i++) { T0 = T1; T1 = T2; T2 = ans; ans = T0 + T1 + T2; } return ans; }
总结
我们总是感觉到递归的优雅,可是在性能方面真的是让人望而生畏 尤其工作后发现递归几乎不会出现,无论是他的易错还是性能都不允许我们使用 如果文章存在问题或者更好的题解,欢迎大家在评论区斧正和评论,各自努力,你我最高处见
这篇关于LeetCode——1137. 第 N 个泰波那契数(Java)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现