无连续 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），仅供参考
企业数字化 ERP 产品动态
相关推荐
redux-form `formValueSelector` 深度指南：从 Redux 状态中优雅提取表单值 redux-form formValueSelector 深度指南：从 Redux 状态中优雅提取表单值 【免费下载链接】redux-form A Higher Order Component using react-redux to keep form state in a Redux store 项目地址: https://gitcode.com/gh_mirrors/re/redux-form
formValue… · 2026/9/23 1:45:54
3个技巧搞定付费电影网API图解原理面试 3个技巧搞定付费电影网API图解原理面试 版本升级后 API 全变了，这种崩溃感谁懂？昨天还在跑通的代码，今天一更新依赖，报错满天飞。这时候光背文档没用，得看 图解原理… · 2026/9/23 10:56:20
WeChatFerry 教程：3 步搭建一个能接大模型的微信机器人 WeChatFerry 教程：3 步搭建一个能接大模型的微信机器人 【免费下载链接】WeChatFerry 微信机器人，可接入DeepSeek、Gemini、ChatGPT、ChatGLM、讯飞星火、Tigerbot等大模型。微信 hook WeChat Robot Hook. 项目地址: https://gitcode.com/GitHub_Trend… · 2026/9/23 10:56:20
GFPGAN图片修复实战：从人脸检测到服务化部署的完整指南 简介：本资源为基于Python深度学习框架的GFPGAN图片修复算法实现源码，面向具备一定Python编程与深度学习基础、希望深入研究图像修复与生成对抗网络的开发者，可用于老旧照片修复、面部图像增强及数字取证等场景。压缩包共62个文件，… · 2026/9/23 10:56:20
基于LSTM的时间序列异常检测原理与工程落地全解析 简介：基于长短期记忆网络的异常检测项目，源自智能运维异常检测竞赛，主要面向人工智能、运维监控以及时序数据挖掘学习者，也适合作为计算机相关专业的毕业设计课题或课程设计参考。压缩包共14个文件，包含3个Python源码&… · 2026/9/23 10:56:14
从一个 Markdown 文件说起：用 TaoToken 统一 Key 打通 AI 工具配置链路 /* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/23 10:56:14
3招搞定手机怎么下载微信面试难题实战项目解析 3招搞定手机怎么下载微信面试难题实战项目解析 面试被问“手机怎么下载微信”背后的原理，90%的人答不上来。别笑，这看似弱智的问题，实则是考察你对移动应用分发机制、安全校验及网络协议理解的试金石。我带过不少校招新人，他们背了八股文，却连一个A… · 2026/9/23 0:00:03
你有新短消息请注意查收：3个新手避坑指南搞定消息系统选型 你有新短消息请注意查收：3个新手避坑指南搞定消息系统选型 面试被问“高并发下如何保证消息不丢失”，你张口就是“用Redis”，结果面试官追问“如果Redis宕机了怎么办”，你瞬间卡壳。这种场景太常见了，很多新手在背八股文时，只记住了技术名词… · 2026/9/23 0:00:29
