TES286 发表于 2021-11-6 01:17

动态规划: 上楼梯

本帖最后由 TES286 于 2021-11-6 11:43 编辑

有这样一个问题

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



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

f(1) = 1

f(2) = 2

而后面的推到如下



也就是

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

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

可以构建以下代码

```python
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) 运行一次

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

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

可以, 代码如下

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

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



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



代码:

```python
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
    else:
      r = b(n-1) + b(n-2)
      l = 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)
```

平淡最真 发表于 2021-11-6 03:43

能打败数学的只有数学了,:victory:
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)

平淡最真 发表于 2021-11-6 03:45

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

魔术使nqy 发表于 2021-11-6 07:28

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

mokson 发表于 2021-11-6 08:13

QingYi. 发表于 2021-11-6 09:16

斐波那契数列

sam喵喵 发表于 2021-11-6 09:28

感谢分享,确实快

trieszhang 发表于 2021-11-6 11:05

崇拜数学大神
页: [1]
查看完整版本: 动态规划: 上楼梯