Leetcode动态规划之PHP解析(70. Climbing Stairs)


2019-5-15 期四  

动态规划题第一天



d73f11103401c528675f5b8990275bbc.png

这是一个爬楼梯的问题,给定一个数字代表着楼梯的层数,每次你可以走一步或者两步,求最终你可以有几种方式到达顶峰。


看了一个专栏提到,关于解动态规划的题目可以从以下几点入手。


   1.递归+记忆化 ->反向推出递推公式。

   2.状态的定义 opt[n],dp[n].

   3.状态转移的方程dp[n]=dp[n-1]+dp[n-2]

   4.最优子结构


我们先用回溯法的思想来解,第n层台阶总的走法就等于它相邻台阶总走法+两阶台阶之外的走法,得出的递推公式.

 f(n)=f(n-1)+f(n-2)


所以代码可以直接写出。

  /**
     * @param Integer $n
     * @return Integer
     */
    function climbStairs($n) {
       if($n<=1){
           return 1;
       }
        return $this->climbStairs($n-1)+$this->climbStairs($n-2);
    }

但是这种递归的话进行了大量重复的运算,我们来看php的运行结果。你可以看到,当n等于44的时候运算超时了。

206592cc30f474ba898aeb796664f1ca.png

动态规划

动态规划最重要的两点就是状态的定义(有点飘)和递推的方程(递推公式很难推,学动态规划需要去大量的实战练习)。

 f[n]=f[n-1]+f[n-2]

递推方程就是一个斐波那契数列

 
    /**
     * @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];
       
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D62 976. Largest Perimeter Triangle

>> 下一篇: Leetcode PHP题解--D63 917. Reverse Only Letters