01串
时间限制:1000 ms | 内存限制:65535 KB
难度:2
ACM的zyc在研究01串,他知道某一01串的长度,但他想知道不含有“11”子串的这种长度的01串共有多少个,他希望你能帮帮他。
注:01串的长度为2时,有3种:00,01,10。
随后有n行,每行有一个整数m(2<=m<=40),表示01串的长度;
2 2 3
3 5
思路:
动态规划基础题,f[n]=f[n-1]+f[n-2](n>=3),当n=1时f[1]=2,当n=2时f[2]=3。
设当前状态为n时,符合条件的01串个数为f[n],则n-1时符合的个数为f[n-1]。n的情况即为在n-1的长度上+1而已,即要不在n-1长度后加0或者加1。无论n-1长度的最后一个数是0还是1,末尾添加0也不影响,故添0的话有f[n-1]个。若添1的话,则n-1长度的最后一个数必不为1,不为1则必为0,为0的话则同刚才添0的情况类似,是前面n-2长度符合条件的个数f[n-2],所以添1的话,个数是f[n-2]。
分析后得出,最后得出n>=3时候的式子f[n]=f[n-1]+f[n-2](n>=3)。
AC:
#include<stdio.h> int main() { int N,i,number; int f[50]; scanf("%d",&N); while(N--) { f[1]=2; f[2]=3; scanf("%d",&number); for(i=3;i<=number;i++) f[i]=f[i-1]+f[i-2]; printf("%d\n",f[number]); } return 0; }
总结:
动态规划基础题,找下感觉,练练手。
相关推荐
8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack 【专辑】插头DP 【专辑】单调队列+斜率优化的DP 01背包问题 acm动态规划总结 PKU——DP专辑 背包之01 POJ 动态规划总结 背包之01背包、完全背包、多重背包详解 ...
动态规划经典题目总结中包括了经典的最长不下降子序列、最长公共子序列、01背包、完全背包、部分背包等算法的详解。 一、最长不下降子序列(LIS) 最长不下降子序列问题是指给定一个序列,找出其中最长的不下降子...
动态规划是一种重要的算法思想,常用于解决复杂度较高的优化问题,尤其在计算机科学和编程面试中占据重要地位。本篇将深入探讨动态规划在LeetCode上的一些经典问题及其解法。 1. **Min Cost Climbing Stairs** ...
### 基础算法之动态规划基础(C++版) #### 动态规划概述 动态规划是一种重要的算法思想,被广泛应用于计算机科学与信息技术领域。它主要用于解决最优化问题,通过分解问题来寻找最佳解决方案。与之前的搜索算法或...
【动态规划】是一种在计算机科学和运筹学中广泛使用的算法设计技术,尤其在解决最优化...动态规划不仅可以应用于上述的竞赛问题,还广泛应用于图论、字符串处理、组合优化等多个领域,是计算机科学中的一个基石概念。
LeetCode动态规划实用知识库分享是一个集合了多种动态规划题目的资源库,涵盖了基础题目、01背包问题、完全背包问题、子序列问题、编辑距离问题等多种类型的动态规划题目。通过学习和实践这些题目,可以帮助开发者和...
### 动态规划总结 #### 1. 按状态类型分类 动态规划问题的核心在于定义合适的状态,根据状态的不同可以将动态规划分为不同的类别。这些分类有助于我们更好地理解和解决问题。 ##### 1.1 编号(长度)动态规划 这...
在具体问题中,"Two Subsequences" 是一个关于01串的优化问题,目标是找到两个子序列,使得两个子序列的压缩函数(即满足特定条件的最短01串)长度之和最小。通过从前向后处理,记录子序列末尾数字的最优值,可以将...
本压缩包文件包含的五个经典算法分别是分治策略、动态规划和回溯法,这些都是解决复杂问题的重要方法。 首先,分治策略是一种将大问题分解为小问题来解决的方法。它通常包含三个步骤:分解、解决和合并。例如,在C#...
动态规划是一种解决问题的有效方法,尤其在计算机科学,尤其是算法设计中...在实际应用中,动态规划也被广泛应用于诸如图论、字符串匹配、最短路径等问题中。学习和掌握动态规划是提升编程能力和算法思维的重要步骤。
动态规划是一种重要的算法思想,广泛应用于解决资源分配、路径优化、最优化问题等。在这个“动态规划100例”中,我们能看到多种经典问题的实例,这些例子涵盖了不同的领域和场景,对于学习和理解动态规划有着极大的...
它支持SPI接口,可以与微控制器如Arduino、AVR、STM32等进行通信,并且具有自动重传和动态数据速率调整等功能,提高了通信的稳定性和效率。 描述中的“物联网/通信技术2.4G无线通信”强调了这个项目的核心内容。...
综合以上所述,"8枚硬币"、"01背包回溯法"和"串匹配问题"这三大主题涉及到了组合优化、动态规划和字符串处理等重要计算机科学概念。通过C++实现,我们可以直观地了解这些问题的解决方案,并在实践中提升编程能力。...
从提供的文件内容中可以看到,ACM竞赛所涉及的知识点相当广泛,涵盖了动态规划、字符串算法、数学专题等多个方面。每个章节都详细介绍了相关的算法模板和专题知识,以下为每个章节的知识点概览: 第一章 动态规划...
- 在本项目中,Virtools主要用于设计消息解释执行的行为模组,使得用户界面能够根据接收到的数据做出动态响应。 - 通过Virtools的Building Blocks机制,可以轻松实现复杂的逻辑处理和动画效果,极大地提升了用户...
6. **动态规划应用**:在处理特定的字符串问题时,如最长公共子串、编辑距离等,动态规划是一种强大的工具。通过构建状态转移矩阵,可以有效地求解这类问题。 7. **字符串的内存管理**:在实际编程中,字符串的内存...
动态规划(DP)是一种强大的算法思想,用于解决最优化问题,通过将复杂问题分解成更小的子问题来求解。以下是对DP问题不完全总结的详细解释: 1. 编号(长度)动态规划: 这类问题的核心在于状态通常由序列的长度或...
1. **算法基础**:这部分通常会讲解基础的数据结构,如数组、链表、栈、队列、树、图等,以及基础算法,如排序、搜索、动态规划、贪心算法等。这些是ACM竞赛中常遇到的问题类型,对解题至关重要。 2. **高级算法**...