`
Simone_chou
  • 浏览: 192843 次
  • 性别: Icon_minigender_2
  • 来自: 广州
社区版块
存档分类
最新评论

01串(动态规划)

    博客分类:
  • NYOJ
 
阅读更多

01串

时间限制:1000 ms  |  内存限制:65535 KB
难度:2
描述

ACM的zyc在研究01串,他知道某一01串的长度,但他想知道不含有“11”子串的这种长度的01串共有多少个,他希望你能帮帮他。

注:01串的长度为2时,有3种:00,01,10。

 
输入
第一行有一个整数n(0<n<=100),表示有n组测试数据;
随后有n行,每行有一个整数m(2<=m<=40),表示01串的长度;
输出
输出不含有“11”子串的这种长度的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;
}

   总结:

   动态规划基础题,找下感觉,练练手。

分享到:
评论
1 楼 沙茶敏 2013-08-05  
给你一个N位01串..求没有连续K个相同数字的序列的个数。例如N=2 K=2 结果为01  10 两个

相关推荐

    经典动态规划合集_牛人 树形,压缩 老题

    8.徐源盛《对一类动态规划问题的研究》 背包九讲Pack 【专辑】插头DP 【专辑】单调队列+斜率优化的DP 01背包问题 acm动态规划总结 PKU——DP专辑 背包之01 POJ 动态规划总结 背包之01背包、完全背包、多重背包详解 ...

    动态规划经典题目

    动态规划经典题目总结中包括了经典的最长不下降子序列、最长公共子序列、01背包、完全背包、部分背包等算法的详解。 一、最长不下降子序列(LIS) 最长不下降子序列问题是指给定一个序列,找出其中最长的不下降子...

    3、动态规划必练题(含解法).pdf

    动态规划是一种重要的算法思想,常用于解决复杂度较高的优化问题,尤其在计算机科学和编程面试中占据重要地位。本篇将深入探讨动态规划在LeetCode上的一些经典问题及其解法。 1. **Min Cost Climbing Stairs** ...

    基础算法 第9章 第1节 动态规划基础(C++版)-2021.01.31.pdf

    ### 基础算法之动态规划基础(C++版) #### 动态规划概述 动态规划是一种重要的算法思想,被广泛应用于计算机科学与信息技术领域。它主要用于解决最优化问题,通过分解问题来寻找最佳解决方案。与之前的搜索算法或...

    历届NOIp动态规划梳理 (54页)--PASCAL 好.pdf

    【动态规划】是一种在计算机科学和运筹学中广泛使用的算法设计技术,尤其在解决最优化...动态规划不仅可以应用于上述的竞赛问题,还广泛应用于图论、字符串处理、组合优化等多个领域,是计算机科学中的一个基石概念。

    LeetCode__动态规划实用知识库分享

    LeetCode动态规划实用知识库分享是一个集合了多种动态规划题目的资源库,涵盖了基础题目、01背包问题、完全背包问题、子序列问题、编辑距离问题等多种类型的动态规划题目。通过学习和实践这些题目,可以帮助开发者和...

    动态规划总结

    ### 动态规划总结 #### 1. 按状态类型分类 动态规划问题的核心在于定义合适的状态,根据状态的不同可以将动态规划分为不同的类别。这些分类有助于我们更好地理解和解决问题。 ##### 1.1 编号(长度)动态规划 这...

    动态规划问题优化模式2_杨志灿.pptx

    在具体问题中,"Two Subsequences" 是一个关于01串的优化问题,目标是找到两个子序列,使得两个子序列的压缩函数(即满足特定条件的最短01串)长度之和最小。通过从前向后处理,记录子序列末尾数字的最优值,可以将...

    c#精典五大算法 分治,动态规划,回溯法

    本压缩包文件包含的五个经典算法分别是分治策略、动态规划和回溯法,这些都是解决复杂问题的重要方法。 首先,分治策略是一种将大问题分解为小问题来解决的方法。它通常包含三个步骤:分解、解决和合并。例如,在C#...

    动态规划课后作业python

    动态规划是一种解决问题的有效方法,尤其在计算机科学,尤其是算法设计中...在实际应用中,动态规划也被广泛应用于诸如图论、字符串匹配、最短路径等问题中。学习和掌握动态规划是提升编程能力和算法思维的重要步骤。

    动态规划100例

    动态规划是一种重要的算法思想,广泛应用于解决资源分配、路径优化、最优化问题等。在这个“动态规划100例”中,我们能看到多种经典问题的实例,这些例子涵盖了不同的领域和场景,对于学习和理解动态规划有着极大的...

    电子-串口NRF24L01P透传.zip

    它支持SPI接口,可以与微控制器如Arduino、AVR、STM32等进行通信,并且具有自动重传和动态数据速率调整等功能,提高了通信的稳定性和效率。 描述中的“物联网/通信技术2.4G无线通信”强调了这个项目的核心内容。...

    最近对,8枚硬币,01背包回溯法,串匹配问题/C++实现,内有报告

    综合以上所述,"8枚硬币"、"01背包回溯法"和"串匹配问题"这三大主题涉及到了组合优化、动态规划和字符串处理等重要计算机科学概念。通过C++实现,我们可以直观地了解这些问题的解决方案,并在实践中提升编程能力。...

    acm从入门到放弃

    从提供的文件内容中可以看到,ACM竞赛所涉及的知识点相当广泛,涵盖了动态规划、字符串算法、数学专题等多个方面。每个章节都详细介绍了相关的算法模板和专题知识,以下为每个章节的知识点概览: 第一章 动态规划...

    串口通信的界面交互性的设计与实现

    - 在本项目中,Virtools主要用于设计消息解释执行的行为模组,使得用户界面能够根据接收到的数据做出动态响应。 - 通过Virtools的Building Blocks机制,可以轻松实现复杂的逻辑处理和动画效果,极大地提升了用户...

    01 SequenceString.rar

    6. **动态规划应用**:在处理特定的字符串问题时,如最长公共子串、编辑距离等,动态规划是一种强大的工具。通过构建状态转移矩阵,可以有效地求解这类问题。 7. **字符串的内存管理**:在实际编程中,字符串的内存...

    DP问题不完全总结.pdf

    动态规划(DP)是一种强大的算法思想,用于解决最优化问题,通过将复杂问题分解成更小的子问题来求解。以下是对DP问题不完全总结的详细解释: 1. 编号(长度)动态规划: 这类问题的核心在于状态通常由序列的长度或...

    HDU_ACM培训课件(完整版)

    1. **算法基础**:这部分通常会讲解基础的数据结构,如数组、链表、栈、队列、树、图等,以及基础算法,如排序、搜索、动态规划、贪心算法等。这些是ACM竞赛中常遇到的问题类型,对解题至关重要。 2. **高级算法**...

Global site tag (gtag.js) - Google Analytics