如何对统计无连续0的n长二进制串的递归代码做记忆化优化

你当前的思路走了弯路：如果只是要统计合法串的数量，完全不需要生成、存储所有完整的二进制串，更不需要用字符串作为记忆化的key，这会带来极高的时空开销。

为什么不需要存储字符串做记忆化 #

你的递归逻辑本质上只依赖两个状态：

• 当前已经构造的串长度
• 串的最后一位是0还是1

不管前面的串是什么内容，只要这两个状态一致，后续能生成的合法串数量完全相同，所以记忆化的key只需要这两个参数即可，和整个字符串无关。

最优记忆化实现方案 #

直接用二维数组做记忆化即可，不需要哈希结构，时空复杂度都能降到O(n)，甚至可以优化到O(1)空间：

状态定义 #

• dp[k][0]：长度为k、最后一位是0的合法二进制串数量
• dp[k][1]：长度为k、最后一位是1的合法二进制串数量

递推规则 #

• 最后一位是0的话，前一位只能是1：dp[k][0] = dp[k-1][1]
• 最后一位是1的话，前一位可以是0或1：dp[k][1] = dp[k-1][0] + dp[k-1][1]

初始条件 #

长度为1的时候，两个串都合法：dp[1][0] = 1, dp[1][1] = 1

结果计算 #

长度为n的合法串总数是dp[n][0] + dp[n][1]，本质就是斐波那契数列，直接按递推算即可，不需要递归回溯。

如果你非要保留递归写法，也可以把递归函数改成返回计数结果，参数只留剩余长度和上一位的值，记忆化用二维数组存已经算过的结果即可，示例代码如下：

// memo[k][0] 表示还剩k位要填，上一位是0时的合法数目，初始值设为-1表示未计算
vector<vector<int>> memo;
int solve(int remain, int last_bit) {
    if(remain == 0) return 1;
    if(memo[remain][last_bit] != -1) return memo[remain][last_bit];
    int res = 0;
    if(last_bit == 0) {
        // 上一位是0，这一位只能填1
        res = solve(remain - 1, 1);
    } else {
        // 上一位是1，这一位可以填0或者1
        res = solve(remain - 1, 0) + solve(remain - 1, 1);
    }
    return memo[remain][last_bit] = res;
}
// 调用时先初始化memo为(n+1)*2的数组，所有值设为-1，调用solve(n, 1) + solve(n, 0)即可得到总数

如果你确实需要生成所有合法串而不是只统计数量，那记忆化对你没有帮助，因为每个合法串都是唯一的，不存在重复的子问题结果可以复用，只能老老实实回溯生成。

内容的提问来源于stack exchange，提问作者Abhijeet Srivastava