解答牛顿爬楼梯问题

今天面试遇到了这个题,脑子轴了一下, 没有答上来, 事后想了想, 其实也是蛮简单的问题

牛顿爬楼梯.png

爬楼梯一次只能迈一节或二节台阶. 假设一共N节台阶. 那么一共有多少种方法呢? 分析问题的关键: 最后一步迈了几个格子? 如果最后一步迈了一个格子: 前面所有步法的数量为f(N-1) 如果最后一步迈了两个格子: 前面所有步法的数量为f(N-2)

"""
一个人一次可以迈过一节楼梯, 或者两节楼梯
问 N节楼梯有多少种走法?
分析: 
1节楼梯有1种走法
2节楼梯有2种走法

3节楼梯的走法数量 = 2节楼梯的走法数量(最后一次走一步的数量) + 1节楼梯的走法数量(最后一次走两步的数量)
N节楼梯的走法数量 = N-1 节楼梯的走法数量 + N-2节楼梯的走法数量

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

"""

def take_1_2_stairs(N):

    if N == 1:
        return 1

    if N == 2:
        return 2

    return take_1_2_stairs(N-1) + take_1_2_stairs(N-2)


"""
f(N) = f(N-1) + f(N-2) + f(N-3)
"""
# 如果最多能迈三节
def take_1_2_3_stairs(N):
    if N == 1:
        return 1
    if N == 2:
        return 2
    if N == 3:
        return 4

    return take_1_2_3_stairs(N-1) + take_1_2_3_stairs(N-2) + take_1_2_3_stairs(N-3)


def main():
    result_1_2 = take_1_2_stairs(10)
    result_1_2_3 = take_1_2_3_stairs(10)
    print("如果每次迈出1-2个台阶, 共有",result_1_2, "种解法")
    print("如果每次迈出1-3个台阶,共有", result_1_2_3, "种走法")

if __name__ == '__main__':
    main()

这里用到了类似斐波那契的递推, 但实际上每次的结果取决于上一次保存的状态,是动态规划法的一种表现形式

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏天天P图攻城狮

Android P之Smart Linkify

如果是自定义模式,则需要调用上面的方法(方法很多,未完全列出来),其核心就是通过正则去匹配,所以这种自定义模式必须要传入一个Pattern值。

24020
来自专栏Flutter入门

H264码流分析导读

H.264的功能分为两层:视频编码层(VCL, Video Coding Layer)和网络提取层(NAL, Network Abstraction Layer...

36610
来自专栏日常学python

WordCloud 中英文词云图绘制,看这一篇就够了

摘要: 当我们手中有一篇文档,比如书籍、小说、电影剧本,若想快速了解其主要内容是什么,则可以采用绘制 WordCloud 词云图,显示主要的关键词(高频词)这种...

75340
来自专栏图形学与OpenGL

实验六 背向面消隐算法

// TODO: add draw code for native data here

15550
来自专栏数据小魔方

Python数据可视化与basemap数据地图系列2——点线图

前一篇介绍了如何使用mpl_toolkits包中的basemap模块制作填充地图,这一节继续分享线图+点图的应用。

21620
来自专栏owent

2018年的新通用伪随机数算法(xoshiro / xoroshiro)的C++(head only)实现

前段时间看到说Lua 5.4用了一种新的通用随机数算法,替换掉本来内部使用的CRT的随机数引擎。我看了一下大致的实现,CPU和空间复杂度任然保持了一个较低的水平...

23020
来自专栏一心无二用,本人只专注于基础图像算法的实现与优化。

SSE图像算法优化系列十二:多尺度的图像细节提升。

无意中浏览一篇文章,中间提到了基于多尺度的图像的细节提升算法,尝试了一下,还是有一定的效果的,结合最近一直研究的SSE优化,把算法的步骤和优化过程分享给大家。...

28180
来自专栏窗户

一个简单的完全信息动态博弈的解答

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址   http://www.cnblogs.com/Colin-C...

47640
来自专栏落影的专栏

OpenGL ES实践教程(五)多重纹理实现图像混合

教程 OpenGL ES实践教程1-Demo01-AVPlayer OpenGL ES实践教程2-Demo02-摄像头采集数据和渲染 OpenGL ES实践...

52340

应用潜在语义分析技术将文档进行3D可视化

这里使用了 WPF(译者注:Windows Presentation Foundation) 的 3D 展示功能来对一个文档集合进行了可视化,这些文...

22890

扫码关注云+社区

领取腾讯云代金券