我的一位 friend 最近被问到这个问题:
您必须计算有多少个长度为“K”的二进制字符串。 约束:每个 0 的左边都有一个 1。
最佳答案
这个问题可以改写: 如果不存在两个连续的 0，但第一个元素应为 1(否则约束失败)，则可能有多少个长度为 K 的二进制序列。让我们忘记第一个元素(我们可以这样做，因为它总是固定的)。 然后我们得到了一个非常著名的任务，听起来像这样:“长度为 K-1 且没有连续 0 的二进制序列有多少个？”可以找到解释，例如here
那么答案将是 F(K+1)，其中 F(K) 是从 (1 1 2 ...) 开始的第 K 个斐波那契数。
关于puzzle - 长度为 k 的可能二进制串的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11948007/