下面用递推方式计算斐波那契数列第 n 项的程序,时间复杂度是O(2n)
int fib(int n) { if (n <= 1) return n; int f0 = 0, f1 = 1, cur = 0; for (int i = 2; i <= n; i++) { cur = f0 + f1; f0 = f1; f1 = cur; } return cur; }
复制链接后可在微信、QQ、小红书等平台粘贴分享;答案与解析在题目页。