技巧：记忆化搜索

结合例题来看：

题目描述

给定三种类型的小球P、Q、R，每种小球的数量分别为np、nq、nr个。现在想将这些小球排成一条直线，但是不允许相同类型的小球相邻，问有多少种排列方法。如若np=2，nq=1，nr=1则共有6种排列方式：PQRP，QPRP，PRQP，RPQP，PRPQ以及PQPR。 如果无法组合出合适的结果，则输出0。



输入

一行以空格相隔的三个数，分别表示为np，nq，nr。



输出

排列方法的数量。

题目限制

时间限制：C/C++语言 1000 MS；其他语言 3000 MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

样例输入

2 1 1
样例输出

6

这个题目一看，稍微想了一会，我就用dfs来做，参数是两个列表，第一个存[np,nq,nr]，第二个存当前用的元素。后来当然是超时了，思路大概还是dfs，超时是因为没有用到记忆化搜索这个技巧。当然@cache也可以，但是只限于参数是非列表的情况，所以当参数不是一个列表的时候，就需要用一个备忘录memo来记忆曾经用过的参数对应的函数值。

具体来说：

①首先创建一个字典memo

②然后用memo去存储dfs(pre,p,q,r)对应的函数值作为value，key当然就是参数(pre,p,q,r)

③在dfs函数中，当参数在memo能够找到时直接调用，不能的话就按老流程来，最后存到memo里去

代码如下：

import sys
for line in sys.stdin:
    # line = input().strip()
    if len(line)<=0:break
    s = line.split(' ')
    np,nq,nr = [int(x) for x in s]
    memo = {}
    def dfs(pre,p,q,r):
        if p+q+r==0:return 1
        if (pre,p,q,r) in memo:return memo[(pre,p,q,r)]
        res = 0
        if pre!=0 and p>0:res+=dfs(0,p-1,q,r)
        if pre!=1 and q>0:res+=dfs(1,p,q-1,r)
        if pre!=2 and r>0:res+=dfs(2,p,q,r-1)
        memo[(pre,p,q,r)] = res
        return res
    ans = 0
    if np>0:ans+=dfs(0,np-1,nq,nr)
    if nq>0:ans+=dfs(1,np,nq-1,nr)
    if nr>0:ans+=dfs(2,np,nq,nr-1)
    print(ans)