无连续 1 的二进制字符串计数Cosmos 动态规划实战【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos本指南以 Cosmos 仓库中 no_consec_ones 模块 的题目说明与源码实现为核心系统讲解统计长度为n、不含连续1的二进制字符串个数这一经典动态规划问题。读者将掌握其状态定义、递推方程的推导过程、O(2·n) 时间复杂度的两种参考实现C 与 Python并理解它为何是斐波那契数列的一个变体。问题陈述给定一个长度n请计算长度为n的二进制字符串中不包含连续两个1的字符串个数。例如当n 3时长度为3的全部合法字符串为000, 001, 010, 100, 101共计5个因此算法应返回5。注意011、110、111均因含有连续1而被排除。期望时间复杂度O(2·n)其中n为二进制字符串的长度。由于每个长度只需线性扫描一遍这也是该问题在动态规划框架下的最优线性解法。题目原文与示例见 code/dynamic_programming/src/no_consec_ones/README.md。动态规划思路按末尾字符拆分状态直接枚举所有2^n个字符串再逐串校验显然不可行指数级复杂度。动态规划的关键在于用末尾字符来归纳状态避免重复计算重叠子问题。对于任意一个长度为i的合法字符串它必然以0或1结尾可以定义两个状态endingZero[i]长度为i、以0结尾且不含连续1的字符串个数endingOne[i]长度为i、以1结尾且不含连续1的字符串个数。于是递推关系为以0结尾可以在任意一个长度为i-1的合法字符串无论以0还是1结尾末尾追加0都不会产生连续1因此endingZero[i] endingZero[i-1] endingOne[i-1]以1结尾只能在以0结尾的长度为i-1的合法字符串末尾追加1若前一位是1追加1就构成连续1因此endingOne[i] endingZero[i-1]边界条件长度为1时字符串0和1均合法故endingZero[1] endingOne[1] 1。最终答案为endingZero[n] endingOne[n]。整个过程与动态规划的核心思想一致——把大问题拆成可复用的小子问题并记住结果这正是 code/dynamic_programming/src/README.md 中对 DP 方法论的描述在本题上的具体体现。C 参考实现仓库中的 no_consec_1.cpp 完整实现了上述递推#include iostream #include vector using namespace std; int countNonConsecutiveOnes(int n) { vectorint endingZero(n), endingOne(n); endingZero[0] endingOne[0] 1; for (int i 1; i n; i) { endingZero[i] endingZero[i - 1] endingOne[i - 1]; endingOne[i] endingZero[i - 1]; } return endingZero[n - 1] endingOne[n - 1]; } int main() { int binaryStringLength; cout Enter the length of binary string: ; cin binaryStringLength; cout \nCount of Binary representations of length binaryStringLength not having consecutive ones ; cout countNonConsecutiveOnes(binaryStringLength) endl; return 0; }实现要点使用两个长度为n的vectorint分别记录以0、1结尾的合法串个数索引0对应长度为1的字符串初值均置为1从i 1到n-1顺序填表严格遵循上面两条递推方程返回endingZero[n-1] endingOne[n-1]即长度为n时的两类状态之和。空间优化提示观察递推式可以发现endingZero[i]和endingOne[i]只依赖i-1时刻的值因此可以进一步把两个数组压缩为两个滚动变量将空间复杂度从 O(n) 降到 O(1)同时保持 O(2·n) 的时间复杂度不变。Python 参考实现仓库中的 no_consec_ones.py 使用同样的递推逻辑给出 Python 版本# A dynamic programming solution for no Consecutive Ones in Binary String problem def noConsecOnes(n): a [0 for x in range(n)] # number of strings ending with 0 b [0 for x in range(n)] # number of strings ending with 1 a[0], b[0] 1, 1 for i in range(1, n): # number of strings ending with 0 is the previous ending with 0 # plus the previous ending with 1 with a 0 added a[i] a[i - 1] b[i - 1] # number of strings ending with 1 is the previous ones ending with # 0 plus a 0 b[i] a[i - 1] return a[n - 1] b[n - 1] # Driver program to test above function print( Number of binary strings of length 5 with no consecutive ones is str(noConsecOnes(5)) )与 C 版一一对应列表a即endingZero列表b即endingOne驱动代码直接以n 5调用并打印结果输出应为Number of binary strings of length 5 with no consecutive ones is 8读者可自行将驱动部分改为input()交互输入即可复现与 C 版一致的命令行体验。与斐波那契数列的联系该问题的一个著名性质是答案序列本身就是斐波那契数列的平移。设F(n)为长度为n的合法字符串个数则F(1) 20、1F(2) 300, 01, 10F(3) 5000, 001, 010, 100, 101F(4) 8、F(5) 13……即F(n) F(n-1) F(n-2)这正是斐波那契递推可结合仓库中 fibonacci.md 的 DP 填表示例对照理解F[i] F[i-1] F[i-2]。这是因为从递推式可推出F(n) endingZero(n) endingOne(n) F(n-1) F(n-2)。因此若只需求总数也可以直接套用斐波那契的滚动迭代写法而endingZero/endingOne双状态写法保留了更清晰的语义便于向更复杂的约束如不能出现11且必须以0开头扩展。复杂度分析与适用前提时间复杂度一次线性填表循环体为 O(1) 的常数次加法总复杂度 O(n)即题目要求的 O(2·n) 量级空间复杂度两数组实现为 O(n)滚动变量优化后可降至 O(1)数据规模由于结果是斐波那契数增长速率约为指数级φⁿφ≈1.618。当n较大例如超过 30时32 位int会溢出需按题目要求改用 64 位整数Clong long/ Python 原生大整数或对结果取模。小结无连续 1 的二进制字符串计数是一个非常适合入门动态规划的经典题目状态定义直观、递推关系简单、边界条件明确且与斐波那契数列深度关联。本文以 Cosmos 仓库的 README 为骨架结合 C 实现 与 Python 实现 完成了从问题建模、递推推导、双语言编码到复杂度与溢出分析的完整闭环读者可直接复制上述代码运行验证。【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 无连续 1 的二进制字符串计数（Cosmos 动态规划实战）
无连续 1 的二进制字符串计数Cosmos 动态规划实战【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos本指南以 Cosmos 仓库中 no_consec_ones 模块 的题目说明与源码实现为核心系统讲解统计长度为n、不含连续1的二进制字符串个数这一经典动态规划问题。读者将掌握其状态定义、递推方程的推导过程、O(2·n) 时间复杂度的两种参考实现C 与 Python并理解它为何是斐波那契数列的一个变体。问题陈述给定一个长度n请计算长度为n的二进制字符串中不包含连续两个1的字符串个数。例如当n 3时长度为3的全部合法字符串为000, 001, 010, 100, 101共计5个因此算法应返回5。注意011、110、111均因含有连续1而被排除。期望时间复杂度O(2·n)其中n为二进制字符串的长度。由于每个长度只需线性扫描一遍这也是该问题在动态规划框架下的最优线性解法。题目原文与示例见 code/dynamic_programming/src/no_consec_ones/README.md。动态规划思路按末尾字符拆分状态直接枚举所有2^n个字符串再逐串校验显然不可行指数级复杂度。动态规划的关键在于用末尾字符来归纳状态避免重复计算重叠子问题。对于任意一个长度为i的合法字符串它必然以0或1结尾可以定义两个状态endingZero[i]长度为i、以0结尾且不含连续1的字符串个数endingOne[i]长度为i、以1结尾且不含连续1的字符串个数。于是递推关系为以0结尾可以在任意一个长度为i-1的合法字符串无论以0还是1结尾末尾追加0都不会产生连续1因此endingZero[i] endingZero[i-1] endingOne[i-1]以1结尾只能在以0结尾的长度为i-1的合法字符串末尾追加1若前一位是1追加1就构成连续1因此endingOne[i] endingZero[i-1]边界条件长度为1时字符串0和1均合法故endingZero[1] endingOne[1] 1。最终答案为endingZero[n] endingOne[n]。整个过程与动态规划的核心思想一致——把大问题拆成可复用的小子问题并记住结果这正是 code/dynamic_programming/src/README.md 中对 DP 方法论的描述在本题上的具体体现。C 参考实现仓库中的 no_consec_1.cpp 完整实现了上述递推#include iostream #include vector using namespace std; int countNonConsecutiveOnes(int n) { vectorint endingZero(n), endingOne(n); endingZero[0] endingOne[0] 1; for (int i 1; i n; i) { endingZero[i] endingZero[i - 1] endingOne[i - 1]; endingOne[i] endingZero[i - 1]; } return endingZero[n - 1] endingOne[n - 1]; } int main() { int binaryStringLength; cout Enter the length of binary string: ; cin binaryStringLength; cout \nCount of Binary representations of length binaryStringLength not having consecutive ones ; cout countNonConsecutiveOnes(binaryStringLength) endl; return 0; }实现要点使用两个长度为n的vectorint分别记录以0、1结尾的合法串个数索引0对应长度为1的字符串初值均置为1从i 1到n-1顺序填表严格遵循上面两条递推方程返回endingZero[n-1] endingOne[n-1]即长度为n时的两类状态之和。空间优化提示观察递推式可以发现endingZero[i]和endingOne[i]只依赖i-1时刻的值因此可以进一步把两个数组压缩为两个滚动变量将空间复杂度从 O(n) 降到 O(1)同时保持 O(2·n) 的时间复杂度不变。Python 参考实现仓库中的 no_consec_ones.py 使用同样的递推逻辑给出 Python 版本# A dynamic programming solution for no Consecutive Ones in Binary String problem def noConsecOnes(n): a [0 for x in range(n)] # number of strings ending with 0 b [0 for x in range(n)] # number of strings ending with 1 a[0], b[0] 1, 1 for i in range(1, n): # number of strings ending with 0 is the previous ending with 0 # plus the previous ending with 1 with a 0 added a[i] a[i - 1] b[i - 1] # number of strings ending with 1 is the previous ones ending with # 0 plus a 0 b[i] a[i - 1] return a[n - 1] b[n - 1] # Driver program to test above function print( Number of binary strings of length 5 with no consecutive ones is str(noConsecOnes(5)) )与 C 版一一对应列表a即endingZero列表b即endingOne驱动代码直接以n 5调用并打印结果输出应为Number of binary strings of length 5 with no consecutive ones is 8读者可自行将驱动部分改为input()交互输入即可复现与 C 版一致的命令行体验。与斐波那契数列的联系该问题的一个著名性质是答案序列本身就是斐波那契数列的平移。设F(n)为长度为n的合法字符串个数则F(1) 20、1F(2) 300, 01, 10F(3) 5000, 001, 010, 100, 101F(4) 8、F(5) 13……即F(n) F(n-1) F(n-2)这正是斐波那契递推可结合仓库中 fibonacci.md 的 DP 填表示例对照理解F[i] F[i-1] F[i-2]。这是因为从递推式可推出F(n) endingZero(n) endingOne(n) F(n-1) F(n-2)。因此若只需求总数也可以直接套用斐波那契的滚动迭代写法而endingZero/endingOne双状态写法保留了更清晰的语义便于向更复杂的约束如不能出现11且必须以0开头扩展。复杂度分析与适用前提时间复杂度一次线性填表循环体为 O(1) 的常数次加法总复杂度 O(n)即题目要求的 O(2·n) 量级空间复杂度两数组实现为 O(n)滚动变量优化后可降至 O(1)数据规模由于结果是斐波那契数增长速率约为指数级φⁿφ≈1.618。当n较大例如超过 30时32 位int会溢出需按题目要求改用 64 位整数Clong long/ Python 原生大整数或对结果取模。小结无连续 1 的二进制字符串计数是一个非常适合入门动态规划的经典题目状态定义直观、递推关系简单、边界条件明确且与斐波那契数列深度关联。本文以 Cosmos 仓库的 README 为骨架结合 C 实现 与 Python 实现 完成了从问题建模、递推推导、双语言编码到复杂度与溢出分析的完整闭环读者可直接复制上述代码运行验证。【免费下载链接】cosmosWorlds largest Contributor driven code dataset | Used in Quark Search Engine, OpenGenus IQ, OpenGenus Visual Project项目地址: https://gitcode.com/gh_mirrors/co/cosmos创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考