动态规划: 上楼梯

TES286

有这样一个问题

有一个人要上楼梯, 每次可以上一个或两个楼梯, 求当有x级阶梯时有多少种上法

我们可以知道当x的值很小时的答案:

f(1) = 1

f(2) = 2

而后面的推到如下

也就是

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

每次都会调用到自身, 这是一个递归

可以构建以下代码

def a(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    return a(n-1) + a(n-2)

这个方法可以解决, 但较为耗时, 例如这里入参35, 总共整了2秒多, 到了40, 直接飙到26秒

那么它就要优化

我们以入参为5是看看

f(5) = f(4) + f(3) = f(3) + f(2) + f(2) + f(1) = f(2) + f(1) + f(2) + f(2) + f(1) = 3 f(2) + 2 f(1)

可见, 在入参为5时, f(2) 运行3次, f(1) 运行一次

那么, 在很高的入参下, 有很多次重复计算

那么这些重复的运算可以省掉吗?

可以, 代码如下

def b(n, *, l=dict()):
  # 因为dict是可变对象,在定义时初始化的一个dict()不会随着函数的运行结束而丢失
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    if n in l:
      return l[n]
    else:
      r = b(n-1) + b(n-2)
      l[n] = r
      return r

经过测试, 40次运算时间在0.003s左右

经过优化后, 时间基本稳在0.01s之下

代码:

import time
def a(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    return a(n-1) + a(n-2)

def b(n, *, l=dict()):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  else:
    if n in l:
      return l[n]
    else:
      r = b(n-1) + b(n-2)
      l[n] = r
      return r

if __name__ == '__main__':
    #func = a
    func = b
    #x = 300
    x = int(input('times:'))
    t1=time.time()
    print(func(x))
    t2=time.time()
    print(t2-t1)

平淡最真

能打败数学的只有数学了，

[Python] 纯文本查看 复制代码

def c(x,y,z,n):
    return (y**(n+1)-z**(n+1))/x
if __name__ == '__main__':
    x=5**0.5
    y=0.5+x/2
    z=0.5-x/2
    aa= int(input('times:'))
    t1=time.time()
    print(int(c(x,y,z,aa)))
    t2=time.time()
    print(t2-t1)

平淡最真

时间是够快，但是结果可能不准，毕竟纯浮点数运算

魔术使nqy

动态规划，明白原理，但到自己写就不知道怎么做了

mokson

如果跨一级走了几步，接着跨二级走了几步，如何算？

QingYi.

斐波那契数列

sam喵喵

感谢分享，确实快

trieszhang

崇拜数学大神