70.md

:pencil2:基础刷题之(70. Climbing Stairs)

. 2019-02-02 吴亲库里 库里的深夜食堂

:pencil2:描述

爬一个指定梯数的楼梯，有多少种方式。规则是每次你只能爬一步或者两步。

---

:pencil2:题目实例

​

给定一个梯数是2,那么有两种方式,1.第一次走一步,第二次走一步 2.一次就走两步

---

:pencil2:题目分析

首先我们考虑最简单的情况，当梯数为1时我们只有一种，也就是直接一步登顶，当梯数为2是，有两种，一是每次只爬一步，两次登顶，第二种直接一次爬两步。 我们可以把跳n层台阶看成是f(n)。当梯数n>2时，第一次跳就有两种不同的选择。如果选择跳一步的话，那么跳上n层台阶种类就等于剩下的f(n-1)总数。如果选择跳两步的话，剩下跳n层台阶种类等于f(n-2).这里得出的结论是当n>2时，f(n)=f(n-1)+f(n-2);上面的分析，其实我们使用的是动态规划，实际上是一个斐波那契数列,又称为黄金分割数列。这里我就不是用递归的方式实现了，递归实现的话容易造成节点的重复性，效率低下，比如说我要求$f(10),就要求$f(9)和$f(8),我要求$f(9),就要求$f(8)和$f(7),这样一层一层的依赖，他会随着n数的增大而剧增，加重了计算机的计算。

---

递归实现的话容易造成节点的重复性，效率低下，比如说我要求$f(10),就要求$f(9)和$f(8),我要求$f(9),就要求$f(8)和$f(7),这样一层一层的依赖，他会随着n数的增大而剧增，加重了计算机的计算。

---

:pencil2:最终实现代码

    function climbStairs($n) {
           if($n<=2){
               return $n;
           }
           $twoBack=1;$oneBack=2;
           $currt=0;
           for($i=3;$i<=$n;$i++){
               $currt=$twoBack+$oneBack;
               $twoBack=$oneBack;
               $oneBack=$currt;
           }
           return $currt;
       }

:pencil2:动态规划

 
    /**
     * @param Integer $n
     * @return Integer
     */
    function climbStairs($n) {
       if($n<=1){
           return 1;
       }
        $res[0]=1;
        $res[1]=1;
        for($i=2;$i<=$n;$i++){
            $res[$i]=$res[$i-1]+$res[$i-2];
        }
        return $res[$n];
       
    }

---

:floppy_disk:(626. Exchange Seats)

---

联系

​