leet_552

README

原题链接

题意化简： n个格子用来填数，每个格子可以填P|L|A，要求：

• A最多出现一次
• 不能有连续三个L出现

问一共有多少种填法？结果对10^9 + 7取模

题解

这道题比较有意思，一开始在想用排列组合来解决这个问题，但是想了会儿没想出来，最后只能求助于别的方法了。我们可以先从A入手，由于最多只能有1个A，所以我们先简化一下问题。假设完全不考虑A的情况，那么问题就可以转化为：

n个格子填数，只能填P|L，不能有三个连续的L出现，有多少种填法

我们用f(n)来表示这个简化后的问题的答案，也就是说，在只能填P或者L，且没有三个连续的L出现的情况下，长度为n的序列一共有f(n)种填法。这时我们再考虑进A，如果最终就是没有放A，那么结果和f(n)一样；如果有一个位置放A，比如：

xxxxxxxxAxxxxxxxxxxx

由于最多只能放一个A，而位置t放了A，A左边的m个格子，右边的t个格子，在放置时就完全不考虑A了，也就变成了上面我们的简化模型。因此很显然这样放一共有f(m)*f(t)种放法。由于一共有n个位置，所以我们枚举每一个位置，把它放成A，它左右两边转化为两个相同子问题，因此答案就是：

∑ f(i)*f(n-i-1)

接下来我们再来看如何求f(i)。由于不考虑A了，所以每个位置要么放P要么放L：

• 如果第i个位置放P，而不管之前怎么放的，P都可以随意放，因此有f(i-1)种放法
• 如果第i个位置想放L，这时能不能放还需要取决于i-1和i-2的放置情况，而f(i)携带的信息不够，我们需要加一维

一个比较巧妙的方法（迷之自信…）是，设前i个格子，最后j个格子都放L，一共有f(i)(j)种放法。如果j取0，实际上相当于最后一格放的是P，而j的取值其实就是(0,1,2)。定义出了状态表示方法，我们来看一下如何转义。

• 当最后一个位置放P，很显然f(i)(0) = f(i-1)(0)+f(i-1)(1)+f(i-1)(2)
• 当最后一个位置放L，如果最后只有一个L，那么f(i)(1) = f(i-1)(0)
• 当最后一个位置放L，如果连续两个L，那么f(i)(2) = f(i-1)(1)

所以长度为i的格子一共有f(i)(0)+f(i)(1)+f(i)(2)种放法。

因此一个简单的记忆化搜索就可以搞定了。