LeetCode困难题赏 - 600.不含连续1的非负整数

本文试从文法角度给出此题的解题思路。

题目

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1的个数，其中$1\leq n \leq 10^9$。

示例：

输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

来源：600. 不含连续1的非负整数 (opens new window)

解析

对于这种涉及到二进制字符串的题目，一般都会采用动态规划的思想来解决，观察本题所规定的二进制字符串，发现可以由以下文法$[1]$给出：

$S\rightarrow 10S | 0S | 0 | 1 | \epsilon$

那么根据该文法，我们自然而然地想到构造一个基于字符串长度的状态表$dp$，其中$dp[k]$表示长度为$k$的不含连续1的二进制字符串的个数，然后根据文法写出状态表的初始值：

dp[0] = 1 # 由 S -> ε 语句给出，表示长度为0的字符串只有一个，即空字符串
dp[1] = 2 # 由 S -> 0 | 1 语句给出，表示长度为1的字符串有两个，即0和1

然后根据文法语句$S\rightarrow 10S | 0S$可知，任何长度为$k$的符合条件的字符串，都是由以下两种规则得到的：

1. 在长度为$k-1$的字符串左侧添加$0$；
2. 在长度为$k-2$的字符串左侧添加$10$。

从而得到状态表的递推式：dp[k] = dp[k - 1] + dp[k - 2]，可以发现，该递推式就是斐波那契的生成式。

到此为止，我们只能得到指定长度的二进制字符串的个数，题目中还有个限定条件是$\leq n$，我们分析一个十进制转化为二进制字符串后的构成：

$5 \rightarrow 101, 16 \rightarrow 1000$

即首个字符肯定为1，也就是文法$[1]$中给出的形如$10S$的字符串，我们直接把十进制上界$n$转化为二进制后，可能会得到两种形式的字符串：

1. $10S_{suffix}$，即第二位为0；
2. $11S_{suffix}$，即第二位为1。

对于第二种形式的正整数$n$，我们只需要计算小于$n$的形如$10S$的字符串对应的解即可，设求解程序为$f(S)$，则有如下的分解方式：

$f(S)=dp[L(g(S))]+f(g(S)_{suffix})$

其中$g(S)$表示不大于$S$的形如$10S$的字符串，$L(S)$表示字符串$S$的长度。

代码

[TODO]

查看带有\LaTeX公式渲染的博客内容：https://blog.simplenaive.cn/#/post/21 (opens new window)