No.0003-CareerCup

Given a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b' and can only have up to two consecutive 'c's.
Example:
findStrings(3) returns 19
since the possible combinations are:
aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb and the invalid combinations are:
abb,bab,bba,bbb,bbc,bcb,cbb,ccc
给出一个长度n，求只包含字母a、b、c，且最多只能有1个b，不包含连续的超过两个的c的，长度为n的字符串的数目。

1. 询问

首先要完全明白题意。根据题目的意思，a和b很好理解，c的约束条件则意味着ccacc这样的是满足的。

2. 分析

暴力破解

把所有abc构成的长度为n的字符串都造出来，然后剔除掉不符合的。复杂度O(3^n)。

为何低效

有在明知道前面已经不可能的情况下还继续去试，这就是暴力破解低效的原因。
假如使用DFS递归，则每一步都需要知道之前的状态，如果每一步再检查整个字符串一次过于低效，于是选择把状态放入参数里面一起带着传下去。什么参数很重要？有没有使用过'b'，和末尾'c'的数目。根据这两个参数，就可以知道如何添加字母。
这是一种解法，但时间复杂度不是很直观。虽然知道比起暴力破解肯定效率提高了很多，但具体多少？
而受到这种思路的启发，可以用DP来解决这个问题。

DP解法

和上面的思路类似，构造三维dp矩阵，dp[i][j][k]，i代表对应字符串的长度，j可选0或1,0表示没有使用b，1表示使用过；k可选012，表示末尾连续c的长度。
因此，在已知上一个dp[i]的情况下，下一个dp[i+1]也可以推导出来：

• dp[i+1][0][0] = dp[i][0]：这表示在之前没有使用'b'的字符串后新添加一个'a'，那么无论之前后面有多少'c'，被'a'分隔之后，现在的末尾连续'c'都是0了。
• dp[i+1][1][0] = dp[i]：假如之前使用过'b'，那么末尾添加'a'，否则添加'b'。
• dp[i+1][0][1] = dp[i][0][0]：要求添加完成之后末尾只能有一个'c'，那么只能在最后加'c'，也就是说之前末尾不是'c'。'b'的使用情况继承。
• dp[i+1][1][1] = dp[i][1][0]：同上。
• dp[i+1][0][2] = dp[i][0][1]：类似地，要有两个'c'，之前需要有一个'c'。
• dp[i+1][1][2] = dp[i][1][1]：同上。

由此，得到所有递推公式。
确定初始边界值：dp[1][0][0] = 1 (a); dp[1][0][1] = 1 (c); dp[1][1][0] = 1 (b); dp[1][1][1],dp[1][0][2],dp[1][1][2]=0。
时间复杂度O(n)，空间复杂度O(n)。

3. 代码

class Solution:
    def findString(self, n):
        if not n:
            return 0
        dp = [[[0] * 3 for _ in range(2)] for _ in range(n + 1)]
        dp[1][0][0] = 1
        dp[1][0][1] = 1
        dp[1][1][0] = 1
        for i in range(2, n + 1):
            dp[i][0][0] = dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]
            dp[i][1][0] = 0
            for k in range(2):
                for h in range(3):
                    dp[i][1][0] += dp[i - 1][k][h]
            dp[i][0][1] = dp[i - 1][0][0]
            dp[i][1][1] = dp[i - 1][1][0]
            dp[i][0][2] = dp[i - 1][0][1]
            dp[i][1][2] = dp[i - 1][1][1]
        ret = 0
        for k in range(2):
            for h in range(3):
                ret += dp[-1][k][h]
        return ret

4. 总结

难度Hard。DP在只求一个数值时确实是非常高效的解法。假如要列出所有符合条件的字符串，可能DFS+递归更加好用。