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

栏目: PHP · 发布时间: 5年前

内容简介:动态规划题第一天

2 0 1 9 -5 -15   期四    

动态规划题第一天

Leetcode动态规划之 <a href='https://www.codercto.com/topics/18749.html'>PHP</a> 解析(70. Climbing Stairs)

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

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

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的时候运算超时了。

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

动态规划

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

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


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Vue.js前端开发

Vue.js前端开发

陈陆扬 / 人民邮电出版社 / 2017-2-1 / CNY 45.00

本书分为10章,包括简介、基础特性、指令、过滤器、过渡、组件、状态管理、常用插件、工程实例和Weex打包。本书从简单的单个实例和基础语法,到工程实例,将系统地讲述Vue.js在项目中的适用场景和具体操作。本书的特点在于案例详实,使读者体会到框架的优点和便捷之处,提升开发效率,最后能将Vue.js运用到实际项目中,避免纸上谈兵的尴尬。一起来看看 《Vue.js前端开发》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具