2018/2/2 20:02:08当前位置推荐好文程序员浏览文章

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

牛顿爬楼梯

爬楼梯一次只能迈一节或二节台阶. 假设一共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()

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

上一篇 目录 已是最后
网友评论