爬楼梯

最近重拾leetcode的感觉，在工作之余添加点乐趣，决定以后每周刷4个题，尽量都更新上来，和大家一起分享，共同进步。以下为第一道题目。

题目描述：

假设你正在爬楼梯。需要n阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定n是一个正整数。

分析：

碰到这种类型的题目，最直接的方式就是从一个台阶开始解答，解答出一定数量的，发现答案其中的规律，形成公式，再编码实现。

1个台阶：1； 2个台阶：2；3个台阶：3；4个台阶：5；5个台阶：8........

从结论可以看出，自三个台阶开始，其方法数量等于前两个方法数量的和，即f(n) = f(n-1) + f(n-2) ,  这其实是个局部解，也许只是巧合，所以我们最好能够证明公式是对的。

当n >= 2时，走楼梯可以分两种情况爬楼：

第一种：第一步爬1个台阶，那么他们后面的爬楼方法数量是f(n-1)；

第二种：第一步爬2个台阶，那么他们后面的爬楼方法数量是f(n-2)；

所以f(n) = f(n-1) + f(n-2)，ok，此时已经确认公式没有问题。

编码：

递归：

直观来看，使用递归方法很容易达成目标，实现如下：

    function climbStairs($n) {    

        if (!is_numeric($n) || $n < 0) {

            return;

        }

        if ($n == 1 || $n == 0) {

            return 1;

        }

        return $this->climbStairs($n-1) + $this->climbStairs($n-2);

    }

非递归：

递归的优点很明显，容易理解，代码总共也没多少行，缺点也很明显，中间楼梯重复计算耗时。

function climbStairs($n) {

    if (!is_numeric($n) || $n < 1) {

        return;

    }

    $result = [];

    for ($i=1; $i <= $n ; $i++) {

        if ($i > 2) {

            $result[$i] = $result[$i-1] + $result[$i-2];

        } else {

            $result[$i] = $i;

        }

    }

    return $result[$i-1];

}

该方法使用了空间换时间的方式，使用中间数组来存储中间台阶的结果，减少计算时间。