经典算法题:爬楼梯 ,以斐波那契数列来解题代码案例

经典算法题:爬楼梯 ,以斐波那契数列来解题代码案例

php  /  管理员 发布于 2020-05-25 09:41:44   671

网上这题的解题思路主要有两种：

1. 动态规划 

2. 斐波那契数列

   
   

因为我们用斐波那契数列来解，所以我主要描述方法2.

斐波那契数列 又称 兔子数列，

指得是：1、1、2、3、5、8、13、21、……，

在数学上它得递推公式是：

F(1)=1，

F(2)=1, 

F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。

放到这个题目中我们可以发现：

二阶楼梯的走法有 2 种：

1 阶 + 1 阶 、 2 阶

三阶楼梯的走法有 3 种：

1 阶 + 1 阶、1 阶 + 2 阶、2 阶 + 1 阶

四阶楼梯的走法有 5 种：

1 阶 + 1 阶 + 1 阶 + 1 阶、1 阶 + 2 阶 + 1 阶、1 阶 + 1 阶 + 2 阶、2 阶 + 2 阶、2 阶 + 1 阶 + 1 阶

……

综上，

我们可以发现 n 阶楼梯有 m 种爬法，且 m 符合斐波那契数列规律.

php代码实现：(两种写法，有兴趣的可以自己研究)

1.
function climbStairs($n) {
     if($n<=2) return $n;
     $dp = [1=>1,2=>2];
     
     foreach(range(3,$n+1) as $v){
        //递归加法，这个爬楼梯就是斐波拉切算法求最后f(n-1)+f(n-2)的和
         $dp[$v] = $dp[$v-1]+$dp[$v-2]; 
     }
       return $dp[$n];
}

2.
function climbStairs($n) {
    if ($n <= 2) return $n;
    $dp = [1 => 1, 2 => 2];
    
    for ($i = 3; $i <= $n; $i++) {
        $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
    }
    return $dp[$n];
}