查找斐波納契數列中第 N 個數。

所謂的斐波納契數列是指：

• 前2個數是 0 和 1 。
• 第?i?個數是第?i-1 個數和第i-2 個數的和。

斐波納契數列的前10個數字是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

樣例

給定?1，返回?0

給定?2，返回?1

給定?10，返回?34

雖然這道題是一道入門級的題目，可是在第一遍做的時候并沒有多想，直接使用的遞歸，然后數據通過95%，顯示的到47的時候就溢出了。經過學習前輩的經驗，該題的收獲如下：

方法1：使用遞歸解，時間復雜度是n的指數級別

方法2：開辟一個長度為(n+1)的數組，時間復雜度為O(n)，空間復雜度為O(n)

?我們計算f(0)、f(1)、f(2)、f(3)。。直到f(n)，將這些計算出來的值保存在一個數組arry[n+1]上，這樣計算斐波那契數列就相當于是一個填表的過程。時間復雜度大大降低

1 int Fibonacci(int n) 2 { 3 if(n<=0) 4 return 0; 5 else if(n==1) 6 return 1; 7 else 8 { 9 //動態創建一個長度為(n+1)的數組 10 int *arry=new int[n+1]; 11 arry[0]=0; 12 arry[1]=1; 13 for(int i=2;i<=n;i++) 14 { 15 arry[i]=arry[i-1]+arry[i-2]; 16 } 17 int result=arry[n]; 18 delete [] arry; 19 return result; 20 } 21 } View Code

c++提供delete []表達式釋放指針所指向的數組空間。delete [] arry;該語句回收了arry所指向的數組，把相應的內存返回給自由存儲區。在關鍵字delete和指針arry之間的方括號[]是必不可少的：它告訴編譯器該指針指向的是自由存儲區中的數組，而非單個對象。delete arry只釋放了arry指針所指向的內存地址，理論上來說會少釋放了內存空間，從而產生內存泄露。

方法3：只保留兩個空間變量，空間復雜度為O(1)，時間復雜度為O(n)

1 class Solution { 2 /** 3 * @param n: an integer 4 * @return an integer f(n) 5 */ 6 public int fibonacci(int n) { 7 // write your code here 8 if( n <= 1 ) { 9 return 0 ; 10 } else if (n ==2 ){ 11 return 1 ; 12 } 13 else { 14 int pre = 0 ; 15 int post = 1 ; 16 int fn = 0 ; 17 for(int i=2 ;i<n;i++){ 18 fn = pre + post; 19 pre = post; 20 post = fn; 21 } 22 return fn; 23 } 24 } 25 }

相關題目： 爬樓梯

假設你正在爬樓梯，需要n步你才能到達頂部。但每次你只能爬一步或者兩步，你能有多少種不同的方法爬到樓頂部？

樣例

比如n=3，1+1+1=1+2=2+1=3，共有3中不同的方法

返回 3

public class Solution {/*** @param n: An integer* @return: An integer*/public int climbStairs(int n) {// write your code hereif (n ==0 ) return 1;//這道題的本質其實和上道題一樣，不過我在做這題的時候忽略了n=0的情況，多多練習，多多加油吧if (n ==1 ) return 1;if (n ==2 ){return 2;} else{int pre = 1;int post = 2;int fn=0;for(int i = 3; i<=n; i++){fn = pre+post;pre = post;post = fn;}return fn;}} }

轉載于:https://www.cnblogs.com/wangnanabuaa/p/4951341.html

總結

以上是生活随笔為你收集整理的fibonacci climbing-stairs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。