文档章节

楼梯台阶

寂寞暴走伤
 寂寞暴走伤
发布于 2016/07/19 19:45
字数 973
阅读 10
收藏 0

问题描述:

一个共有10个台阶的楼梯,从下面走到上面,一次只能迈一个台阶或两个台阶,并且不能后退,走完这个楼梯共有多少种方法。


我的代码:

def lt(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    else:
        return lt(n-2)+lt(n-1)
print lt(10)

结果:

89


思路:

借鉴了这篇文章:http://www.lxway.com/522841804.htm

刚开始做的时候,想了传统的方法,可是想到最后觉得一昧求的话太麻烦了,而且太难实现了,网上搜了一下才知道这是典型的递归问题,整个人就豁然开朗了;而且这次不是从下向上递归,而是上往下递归的,即最后是一步上1个台阶的话,之前上了n-1个台阶,走法为f(n-1)种,而最后是一步上2个台阶的话,之前上了n-2个台阶,走法为f(n-2)种,故而f(n)=f(n-1)+f(n-2)


示例代码(修改后):

def fun(n):
    res = fun.cache.get(n, None)
    if res:
        return res
    res = []
    for step in (1, 2):
        if n < step: break
        for p in fun(n - step):
            res.append([step] + p)
    fun.cache[n] = res
    return res
fun.cache = {0:[[]]}
print len(fun(10))
print fun(10)

结果:

89
[[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 2, 1], [1, 1, 1, 1, 1, 1, 2, 1, 1],

[1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 2, 1, 1, 1], [1, 1, 1, 1, 1, 2, 1, 2], [1, 1, 1, 1, 1, 2, 2, 1],

[1, 1, 1, 1, 2, 1, 1, 1, 1], [1, 1, 1, 1, 2, 1, 1, 2], [1, 1, 1, 1, 2, 1, 2, 1], [1, 1, 1, 1, 2, 2, 1, 1],

[1, 1, 1, 1, 2, 2, 2], [1, 1, 1, 2, 1, 1, 1, 1, 1], [1, 1, 1, 2, 1, 1, 1, 2], [1, 1, 1, 2, 1, 1, 2, 1],

[1, 1, 1, 2, 1, 2, 1, 1], [1, 1, 1, 2, 1, 2, 2], [1, 1, 1, 2, 2, 1, 1, 1], [1, 1, 1, 2, 2, 1, 2], [1, 1, 1, 2, 2, 2, 1],

[1, 1, 2, 1, 1, 1, 1, 1, 1], [1, 1, 2, 1, 1, 1, 1, 2], [1, 1, 2, 1, 1, 1, 2, 1], [1, 1, 2, 1, 1, 2, 1, 1],

[1, 1, 2, 1, 1, 2, 2], [1, 1, 2, 1, 2, 1, 1, 1], [1, 1, 2, 1, 2, 1, 2], [1, 1, 2, 1, 2, 2, 1], [1, 1, 2, 2, 1, 1, 1, 1],

[1, 1, 2, 2, 1, 1, 2], [1, 1, 2, 2, 1, 2, 1], [1, 1, 2, 2, 2, 1, 1], [1, 1, 2, 2, 2, 2], [1, 2, 1, 1, 1, 1, 1, 1, 1],

[1, 2, 1, 1, 1, 1, 1, 2], [1, 2, 1, 1, 1, 1, 2, 1], [1, 2, 1, 1, 1, 2, 1, 1], [1, 2, 1, 1, 1, 2, 2],

[1, 2, 1, 1, 2, 1, 1, 1], [1, 2, 1, 1, 2, 1, 2], [1, 2, 1, 1, 2, 2, 1], [1, 2, 1, 2, 1, 1, 1, 1], [1, 2, 1, 2, 1, 1, 2],

[1, 2, 1, 2, 1, 2, 1], [1, 2, 1, 2, 2, 1, 1], [1, 2, 1, 2, 2, 2], [1, 2, 2, 1, 1, 1, 1, 1], [1, 2, 2, 1, 1, 1, 2],

[1, 2, 2, 1, 1, 2, 1], [1, 2, 2, 1, 2, 1, 1], [1, 2, 2, 1, 2, 2], [1, 2, 2, 2, 1, 1, 1], [1, 2, 2, 2, 1, 2],

[1, 2, 2, 2, 2, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [2, 1, 1, 1, 1, 1, 1, 2], [2, 1, 1, 1, 1, 1, 2, 1],

[2, 1, 1, 1, 1, 2, 1, 1], [2, 1, 1, 1, 1, 2, 2], [2, 1, 1, 1, 2, 1, 1, 1], [2, 1, 1, 1, 2, 1, 2], [2, 1, 1, 1, 2, 2, 1],

[2, 1, 1, 2, 1, 1, 1, 1], [2, 1, 1, 2, 1, 1, 2], [2, 1, 1, 2, 1, 2, 1], [2, 1, 1, 2, 2, 1, 1], [2, 1, 1, 2, 2, 2],

[2, 1, 2, 1, 1, 1, 1, 1], [2, 1, 2, 1, 1, 1, 2], [2, 1, 2, 1, 1, 2, 1], [2, 1, 2, 1, 2, 1, 1], [2, 1, 2, 1, 2, 2],

[2, 1, 2, 2, 1, 1, 1], [2, 1, 2, 2, 1, 2], [2, 1, 2, 2, 2, 1], [2, 2, 1, 1, 1, 1, 1, 1], [2, 2, 1, 1, 1, 1, 2],

[2, 2, 1, 1, 1, 2, 1], [2, 2, 1, 1, 2, 1, 1], [2, 2, 1, 1, 2, 2], [2, 2, 1, 2, 1, 1, 1], [2, 2, 1, 2, 1, 2],

[2, 2, 1, 2, 2, 1], [2, 2, 2, 1, 1, 1, 1], [2, 2, 2, 1, 1, 2], [2, 2, 2, 1, 2, 1], [2, 2, 2, 2, 1, 1], [2, 2, 2, 2, 2]]


问题出处:http://www.cheemoedu.com/exercise/29

© 著作权归作者所有

上一篇: 水仙花数
下一篇: 百鸡百钱
寂寞暴走伤
粉丝 0
博文 40
码字总数 20969
作品 0
南阳
运维
私信 提问
Leetcode-Easy 70. Climbing Stairs

21. Merge Two Sorted Lists 描述: 有n阶楼梯,每步只能走1个或2个台阶,请问到达第n阶楼梯一共有多少走法? 思路: 动态规划 程序从 i=3 开始迭代,一直到 i=n 结束。每一次迭代,都会计算...

致Great
2018/03/20
0
0
解答牛顿爬楼梯问题

今天面试遇到了这个题,脑子轴了一下, 没有答上来, 事后想了想, 其实也是蛮简单的问题 爬楼梯一次只能迈一节或二节台阶. 假设一共N节台阶. 那么一共有多少种方法呢? 分析问题的关键: 最后一步...

木子昭
2018/02/02
0
0
小孩上楼梯的方式的种类

例3:一共有10级,每次可走一步也可以走两步.必须要8步走完10级楼梯. 问:一共有多少种走法? 分析:走一步的需要6次,走两步的需要2次。因此,本题是6个1、2个2的组合问题。在6个一步中,插入2...

一贱书生
2016/11/22
6
0
动态规划1-------“幻听症患者”的上台阶

我叫关小破,是一个轻微幻听症患者。 今天上午9点15分,收到女友瑾儿发来的语音,她约我到LTG咖啡馆见面,说是要带我去一家新开的心境诊所,名字听上去很像是看心理或者精神问题的。 女朋友定...

AiFan
2017/11/18
0
0
Leetcode#70. Climbing Stairs(爬楼梯)

题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1: 示例 2: 思路 思路一:...

武培轩
2018/09/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

数组算法

/*数组的相关的算法操作:1、在数组中找最大值/最小值*/class Test11_FindMax{public static void main(String[] args){int[] array = {4,2,6,8,1};//在数组中找最大...

architect刘源源
26分钟前
0
0
okhttp3 以上版本在安卓9.0无法请求数据的解决方案

应用官方的说明:在 Android 6.0 中,我们取消了对 Apache HTTP 客户端的支持。 从 Android 9 开始,默认情况下该内容库已从 bootclasspath 中移除且不可用于应用。且Android P 限制了明文流量...

chenhongjiang
今天
5
0
简单示例:NodeJs连接mysql数据库

开篇引用网上的说法: 简单的说 Node.js 就是运行在服务端的 JavaScript。Node.js 是一个基于Chrome JavaScript 运行时建立的一个平台。Node.js是一个事件驱动I/O服务端JavaScript环境,基于...

李朝强
今天
8
0
大数据学习路线

年薪30W大数据学习路线图: 一、Hadoop入门,了解什么是Hadoop 1、Hadoop产生背景 2、Hadoop在大数据、云计算中的位置和关系 3、国内外Hadoop应用案例介绍 4、国内Hadoop的就业情况分析及课程...

陈小君
今天
3
0
解读 Kylin 3.0.0 | 更敏捷、更高效的 OLAP 引擎

在近期的 Apache Kylin Meetup 成都站上,我们邀请到 Kyligence 架构师 & Apache Kylin Committer 倪春恩对 Kylin 3.0.0 版本的一些重要功能及改进从使用到原理进行了介绍: Apache Kylin 在...

ApacheKylin
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部