洛谷_P1464 Function

洛谷_P1464 Function_python写法

1.错误解法

2.学习记忆化搜索算法

2.1简介

2.2案例学习

3.解法

4.总结

1.错误解法

a = 0
b = 0
c = 0
def w(a,b,c):
    if a<=0 or b<=0 or c<=0:
        return 1
    elif a>20 or b>20 or c>20:
        return w(20,20,20)
    elif a<b and b<c:
        return w(a-1,b,c) + w(a-1,b,c) + w(a-1,b,c-1) -w(a-1,b-1,c-1)
    else:
        return w(a-1,b,c) + w(a-1,b-1,c) + w(a-1,b,c-1) - w(a-1,b-1,c-1)
while 1:
    a, b, c = map(int, input().split(' '))
    if a==-1 and b==-1 and c==-1:
        break
    else:
        print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

直接按照题目地意思来做地话，就会超时。

怎么优化，我也不会，那就先去学习吧。再见

看到网上的C++解法说用的是记忆化搜索算法，那就先学习一下看看记忆化算法是个什么事儿。

2.学习记忆化搜索算法

2.1简介

看完网上有挂记忆化算法的介绍之后，我的~~胡说八道~~是，记忆化算法是一种动态规划算法，它能够存储已经计算过的状态信息，避免造成重复计算，从而能够提高算法的效率。

看到网上有一个更加生动的解释，所谓的记忆化搜索可以理解为是拥有一个备忘录的递归，而记忆化的实现就是通过这个备忘录，在每次进入递归的时候都会先看看备忘录中是否已经计算了，如果没有就计算，有的话就可以直接使用。

2.2案例学习

思路：

1.定义一个备忘录；

2.每次进入递归，看看备忘录是否有；

3.如果没有，每次返回的时候，将计算的值加入备忘录中。

定义备忘录在python中我们可以利用列表来实现。

在定义列表的时候代码中用到了列表推导式，列表推导式

Python进阶：列表推导式（List Comprehension） - 知乎 (zhihu.com)

n = int(input())

def fib(n):
    l = [0 for i in range(n+1)]
    return fib_helper(l,n)

def fib_helper(l,n):
    if n == 0 or n == 1:
        return n
    if l[n] == 0:
        l[n] = fib_helper(l,n-1) + fib_helper(l,n-2)
        return l[n]
    else:
        return l[n]

print(fib(n))

3.解法

         终于给写出来了，大家一定要认真看题目，计算错了让我找错误找了好久好久呜呜呜呜呜....

        我这里定义的备忘录就是一个三维的列表，关于三维列表的访问大家可以自己尝试写一个简单的三维列表，然后看看他是怎么访问的。

        关于内部的判断，如果按照以前的进行嵌套判断的话，还是会超时，所以就增加了一个并列条件：

elif l[a][b][c]:
return l[a][b][c]

data = []
l = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]
def w_helper(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return w_helper(20,20,20)
    elif l[a][b][c]:
        return l[a][b][c]
    elif a<b and b<c:
        l[a][b][c] = w_helper(a,b,c-1) + w_helper(a,b-1,c-1) - w_helper(a,b-1,c)
    else:
        l[a][b][c] = w_helper(a-1,b,c) + w_helper(a-1,b-1,c) + w_helper(a-1,b,c-1) - w_helper(a-1,b-1,c-1)
    return l[a][b][c]

while True:
    a, b, c = map(int, input().split(' '))
    data.append([a,b,c])
    if a == -1 and b == -1 and c == -1:
        data.pop()
        break
for i in data:
    print(f'w({i[0]}, {i[1]}, {i[2]}) = {w_helper(i[0], i[1], i[2])}')