題目：
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

翻譯：
你在爬一個樓梯。到達頂部有n級階梯。
每次你可以選擇爬一級或者二級。在多少不同的方式去到達頂部？

分析：
當n=1，無疑只有一種方式，s=1。
n=2，s=2。
n=3，s=3。
n=4，s=5。
我們發(fā)現(xiàn)這個實際是一個斐波那契數(shù)列。第一反應(yīng)是遞歸實現(xiàn)，f(n)=f(n-1)+f(n-2)，但是遞歸實現(xiàn)，有多次重復(fù)計算，比如在計算f(n-1)時，需要使用f(n-2)+f(n-3)，但是這個時候另一個遞歸調(diào)用已經(jīng)去算了f(n-2)，相當于f(n-2)被計算了2次，這種重復(fù)計算的情況普遍存在，將會浪費大量計算時間。很自然的想到反過來操作，遞歸是從目標算到基礎(chǔ)值，而我們可以采用迭代從基礎(chǔ)值1,2累加上去。

代碼1（遞歸）：

public class Solution {public int climbStairs(int n) {if(n==1||n==2){return n;}else{return climbStairs(n-2)+climbStairs(n-1);}} }

代碼2（迭代）：

public class Solution {public int climbStairs(int n) {if(n==1||n==2){return n;}int n1=1;int n2=2;for(int i=3;i<=n;i++){int temp=n1+n2;n1=n2;n2=temp;}return n2;} }

總結(jié)

以上是生活随笔為你收集整理的Leet Code OJ 70. Climbing Stairs [Difficulty: Easy]的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。