动态规划: 上楼梯
本帖最后由 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)
``` 能打败数学的只有数学了,: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) 时间是够快,但是结果可能不准,毕竟纯浮点数运算 动态规划,明白原理,但到自己写就不知道怎么做了 斐波那契数列 感谢分享,确实快 崇拜数学大神
页:
[1]