大家都知道斐波那契數(shù)列,現(xiàn)在要求輸入一個正整數(shù) n ,請你輸出斐波那契數(shù)列的第 n 項。 斐波那契數(shù)列是一個滿足 的數(shù)列 數(shù)據(jù)范圍: 要求:空間復(fù)雜度 ,時間復(fù)雜度 ,本題也有時間復(fù)雜度 的解法
輸入描述:
一個正整數(shù)n
輸出描述:
輸出一個正整數(shù)。
示例1
說明
根據(jù)斐波那契數(shù)列的定義可知,fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3,所以答案為3。
加載中...