解答牛顿爬楼梯问题

作者: zhaoolee | 来源:发表于2018-02-02 19:33 被阅读157次

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

牛顿爬楼梯.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()

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

相关文章

  • 解答牛顿爬楼梯问题

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

  • 记一次今日头条视频技术面试

    1.题目:继承 解答: 2.题目: 解答: 3.假设某个楼梯有n级,小明要爬上楼梯,小明爬楼梯的时候可能一次走1步...

  • 2019.5.28《禅与摩托车维修艺术》

    知识收获:1,这真是一场独力作战的苦仗,就好像牛顿当年尝试解答“瞬时变化速率”的问题时所面临的困扰 2,困难在于,...

  • 深度学习笔记—模型优化

    [问题] 深度模型中的优化问题部分 1.牛顿法 神经网络中最广泛使用的二阶方法:牛顿法 牛顿法解决了哪些问题? 二...

  • 爬楼梯问题

    接触DP最早的应该就是这道题了吧,翻了翻leetcode submission发现最早的是在一年前... 而且是最...

  • 爬楼梯问题

    今天看到一个斐波纳切问题的变形,觉得很有意思,遂记录一下: 一个青蛙爬楼梯,他可以一次跳一节台阶,也可以跳两节,还...

  • LeetCode中动态规划问题的做题记录

    常规动态规划问题 相关题目: 70.爬楼梯 70.爬楼梯 描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每...

  • 牛吃草问题

    【含义】 “牛吃草”问题是大科学家牛顿提出的问题,也叫“牛顿问题”。这类问题的特点在于要考虑草边吃边长这个因素。 ...

  • 相对论到底说了啥?解决了什么问题?我来告诉你

    主要解决了牛顿没有解决的问题,牛顿虽然厉害,但是他也不知道下面这几个问题该如何是好,今天开始我们比牛顿还聪明了。 ...

  • Newton's method and Quasi Ne

    Welcome To My Blog 牛顿法和拟牛顿法是求解无约束最优化问题的常用方法,优点是收敛速度快.牛顿法...

网友评论

本文标题:解答牛顿爬楼梯问题

本文链接:https://www.haomeiwen.com/subject/xrnezxtx.html