也是记忆数组的优化，python是不是本身就会耗时多一些？

ShiShen_hu @ 2024-11-25 14:43:49

def fun(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1

    if a > 20 or b > 20 or c > 20:
        return fun(20, 20, 20)

    if a < b < c:
        return fun(a, b, c - 1) + fun(a, b - 1, c - 1) + fun(a, b - 1, c)

    if not Memory[a][b][c]:
        value = fun(a - 1, b, c) + fun(a - 1, b - 1, c) + fun(a - 1, b, c - 1) - fun(a - 1, b - 1, c - 1)
        Memory[a][b][c] = value

    return Memory[a][b][c]

data = []
Memory = [[[None for x in range(21)] for i in range(21)] for j in range(21)]
a = 1
while True:
    a, b, c = map(int, input().split())
    if a < 0: break
    data.append((a, b, c))

for i in data:
    print(f"w({i[0]}, {i[1]}, {i[2]}) =", fun(i[0], i[1], i[2]))

by ltz1415 @ 2024-11-25 14:51:47

不管你写什么代码，python都比C++慢

by bcdmwSjy @ 2024-11-25 14:55:12

@ShiShen_hu

记忆化搜索使用 lru_cache。

import functools

@functools.lru_cache(maxsize=None)
def fun(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return fun(20, 20, 20)
    elif a < b < c:
        return fun(a, b, c - 1) + fun(a, b - 1, c - 1) - fun(a, b - 1, c)
    else:
        return fun(a - 1, b, c) + fun(a - 1, b - 1, c) + fun(a - 1, b, c - 1) - fun(a - 1, b - 1, c - 1)

while True:
    a, b, c = map(int, input().split())
    if a==-1 and b==-1 and c==-1: break
    print(f"w({a}, {b}, {c}) =", fun(a,b,c))

by lusers @ 2024-11-25 14:59:32

@ShiShen_hu

记忆化判断太晚：

def fun(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1

    if a > 20 or b > 20 or c > 20:
        return fun(20, 20, 20)

    if Memory[a][b][c] is not None:
        return Memory[a][b][c]

    if a < b < c:
        value = fun(a, b, c - 1) + fun(a, b - 1, c - 1) - fun(a, b - 1, c)
    else:
        value = fun(a - 1, b, c) + fun(a - 1, b - 1, c) + fun(a - 1, b, c - 1) - fun(a - 1, b - 1, c - 1)
    Memory[a][b][c] = value
    return value

data = []
Memory = [[[None for x in range(21)] for i in range(21)] for j in range(21)]
a = 1
while True:
    a, b, c = map(int, input().split())
    if a == b == c == -1:
        break
    data.append((a, b, c))

for i in data:
    print(f"w({i[0]}, {i[1]}, {i[2]}) =", fun(i[0], i[1], i[2]))

也可以直接使用 @functools.cache 或 @functools.lru_cache

by ShiShen_hu @ 2024-11-25 17:23:51

@bcdmwSjy好的好的，感谢大佬

by ShiShen_hu @ 2024-11-25 17:24:25

@lusers好的好的，谢谢大佬