工作8年没涨工资，面试外企给涨了50%。为了给领导面子，我说内部涨薪30%我就留下，结果领导说:就你这水平，涨15%都多!

算法题：记忆函数

递归一跑，CPU 风扇先急了。

这种题我第一眼不会先想着改公式，公式一般没问题，问题多半在重复算。w(15,15,15) 往下拆，一层套一层，很多状态其实早就算过了，但普通递归不认账，每次都从头来。

题目里的函数大概长这样：

w(a,b,c)

有几条规则：

a<=0 or b<=0 or c<=0 -> 1
a>20 or b>20 or c>20 -> w(20,20,20)
a<b<c -> w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)
其他情况 -> w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)

这题麻烦不在递归写不出来，而在它会把同一个参数反复拆。

比如 w(10,10,10) 里面会算到 w(9,10,10)，别的分支也可能算到它。你不缓存，它就老老实实再跑一遍。跑小数据没感觉，数据一大，直接卡住。

我一般处理这种题，就加一张表。算过的 (a,b,c)，下次直接拿。

cache = {}

defw(a, b, c):
    key = (a, b, c)

if key in cache:
return cache[key]

if a <= 0or b <= 0or c <= 0:
        ans = 1
elif a > 20or b > 20or c > 20:
        ans = w(20, 20, 20)
elif a < b < c:
        ans = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
else:
        ans = (
            w(a - 1, b, c)
            + w(a - 1, b - 1, c)
            + w(a - 1, b, c - 1)
            - w(a - 1, b - 1, c - 1)
        )

    cache[key] = ans
return ans

这里有个小细节，key 要放在最前面查。别等分支判断完了再查，那就晚了。

完整输入输出可以这么写：

import sys

memo = {}

defw(a, b, c):
    key = (a, b, c)
if key in memo:
return memo[key]

if a <= 0or b <= 0or c <= 0:
        res = 1
elif a > 20or b > 20or c > 20:
        res = w(20, 20, 20)
elif a < b < c:
        res = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
else:
        res = (
            w(a - 1, b, c)
            + w(a - 1, b - 1, c)
            + w(a - 1, b, c - 1)
            - w(a - 1, b - 1, c - 1)
        )

    memo[key] = res
return res


for line in sys.stdin:
    a, b, c = map(int, line.split())
if a == -1and b == -1and c == -1:
break

    print(f"w({a}, {b}, {c}) = {w(a, b, c)}")

这段代码不花哨，但够稳。

有些同学会直接开三维数组，也行。因为超过 20 的都会压成 w(20,20,20)，真正有效状态就那么点。但用字典写起来更顺，不用处理负数下标，也不怕输入里冒出来 -5 7 9 这种东西。

这类题别被名字唬住，“记忆函数”其实就是记忆化搜索。

递归负责把问题拆开，缓存负责让它别重复干活。少了缓存，它是暴力递归；加上缓存，才像个能上线的版本。