2020-05-17-Go和PHP 实现爬楼梯算法

layout: posttitle: Go和PHP 实现爬楼梯算法
subtitle: Go和PHP 实现爬楼梯算法
date: 2020-05-17
author: he xiaodong
header-img: img/default-post-bg.jpg
catalog: true
tags:
- Go
- PHP
- LeetCode
- 爬楼梯算法
- 动态规划
- 斐波那契数列

原文链接：go lettcode，php 代码个人原创

爬楼梯（Climbing-Stairs）

题干：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
   
2. 2 阶
   示例 2：
   输入： 3
   输出： 3
   解释： 有三种方法可以爬到楼顶。
   
3. 1 阶 + 1 阶 + 1 阶
   
4. 1 阶 + 2 阶
   
5. 2 阶 + 1 阶
   来源：力扣

这题 爬楼梯 算是算法题里面比较经典的。

解题思路

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

1.动态规划
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 符合 斐波那契数列 规律，所以直接上代码咯！

Go 实现

// 斐波那契数列
// 1 1 2 3 5 8 13 ....
func climbStairs2(n int) int {
    // 1 阶台阶直接返回 1
    if n == 1 {
        return 1
    }
    // 2 阶台阶直接返回 2
    if n == 2 {
        return 2
    }
    current := 2
    pre := 1
    // 当前台阶的走法是前两个台阶走法之和
    for i := 3; i <= n;i ++ {
        current = current + pre
        pre = current - pre
    }
    return current
}

PHP 实现，一共两版实现，看自己喜欢哪种代码吧

function climbStairs($n) {
    // if($n==1) return 1;
    // $dp[1]=1;
    // $dp[2]=2;
    // for($i=3;$i<=$n;$i++){
    //     $dp[$i]=$dp[$i-1]+$dp[$i-2];
    // }
    // 
    // return $dp[$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];
}

最后恰饭 阿里云全系列产品/短信包特惠购买 中小企业上云最佳选择 阿里云内部优惠券