[LeetCode]Non-negative Integers without Consecutive Ones

我们先考虑长度为n的bit有多少满足条件没有连续1的数字，用dp[i]表示长度为i的bit可以表示的没有连续1的数字的个数。我们可以推出递推公式：

• 按照MSB(most significant bit)的顺序，假设第i位数字为1，那么i-1位数字可以取0或者1，所以dp[i + 1] += dp[i]
• 如果第i位数字为0，那么i - 1位数字只能取1，所以dp[i + 1] += dp[i - 1]
• 综合起来，我们有dp[i] = dp[i - 1] + dp[i - 2]，是斐波那契数列的公式

那么剩下的问题就是，给定num，我们如何寻找小于等于num并且没有连续1的数字的数量。假设num的二进制位0101 0010，我们从左向右扫：

• 当我们碰到第一个1的时候，我们不知道有多少大于0100 0000的valid的数，我们可以算出0000 0000 - 0011 1111符合条件的数的数量，这些数都是小于num的，这个值为dp[6]
• 当我们碰到第二个1的时候，同理我们可以算出0100 0000 - 0100 1111的数，值为dp[4]
• 碰到第三个1，同理我们可以算出0101 0000 - 0101 0001的数，值为dp[1]
• 以上的区间合起来都是连续的，最后我们再统计0101 0010自身，所以答案是dp[6] + dp[4] + dp[1] + 1

那么当num会出现连续1的时候，比如0101 1010:

• 扫到第一个1，统计0000 0000 - 0011 1111, dp[6]
• 扫到第二个1，统计0100 0000 - 0100 1111, dp[4]
• 扫到第三个1，统计0101 0000 - 0101 0111, dp[3]
• 剩下的01011xxx都是不符合条件的了，所以结果为dp[6] + dp[4] + dp[3]

我们的思路就和这是一样的，我们从左到右扫，如果扫到第i位(从右到左)1，我们把其固定为0，其右边剩下i位可以有dp[i]个合理的数字。之后我们再把其变回1，继续扫，依次类推，如果出现了11，我们就可以直接return了，否则说明num自身也是一个满足条件的数，我们要加1。时间复杂度O(32)，代码如下：