青蛙爬台階問題的三種解法-Python

題意描述

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層高台階的方法？

思路分析：

這個問題有三種方法來解決，並在下面給出三處方法的python實現

方法1:遞歸

設青蛙跳上n級台階有f(n)種方法，把這n種方法分為兩大類，第一種最後一次跳了一級台階，這類方法共有f(n-1)種，第二種最後一次跳了兩級台階，這種方法共有f(n-2)種，則得出遞推公式f(n)=f(n-1)+f(n-2),顯然，f(1)=1,f(2)=2，遞推公式如下：

* 這種方法雖然代碼簡單，但效率低，會超出時間上限*

代碼實現如下

class Solution:n # @param {integer} nn # @return {integer}n def climbStairs(self, n):n if n==1:n return 1n elif n==2:n return 2n else:n return self.climbStairs(n-1)+self.climbStairs(n-2)n

方法2: 用循環來代替遞歸

這種方法的原理仍然基於上面的公式，但是用循環代替了遞歸，比上面的代碼效率上有較大的提升，可以AC

代碼實現如下：

class Solution:n # @param {integer} nn # @return {integer}n def climbStairs(self, n):n if n==1 or n==2:n return nn a=1;b=2;c=3n for i in range(3,n+1):n c=a+b;a=b;b=cn return cn n

方法三：建立簡單數學模型，利用組合數公式

這種方法我比較喜歡

設青蛙跳上這n級台階一共跳了z次，其中有x次是一次跳了兩級，y次是一次跳了一級，則有z=x+y ,2x+y=n,對一個固定的x，利用組合可求出跳上這n級台階的方法共有

種方法

python代碼實現如下：

class Solution:n # @param {integer} nn # @return {integer}n def climbStairs(self, n):n def fact(n):n result=1n for i in range(1,n+1):n result*=in return resultn total=0n for i in range(n/2+1):n total+=fact(i+n-2*i)/fact(i)/fact(n-2*i)n return total n

Python學習群：593088321

推薦閱讀：