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背包、完全背包、多重背包详解 ...
动态规划一般可分为线性动规,区域动规,树形动规,背包动规四类。 举例: 线性动规:拦截导弹,合唱队形,挖地雷,建学校,剑客决斗等; 区域动规:石子合并, 加分二叉树,统计单词个数,炮兵布阵等; 树形动规:...
实验3 最长公共子序列(包括动态规划法) 实验4 最大子段和问题(包括蛮力算法、分治算法和动态规划算法) 实验5 背包、01背包问题(包括贪心算法和分治算法) 实验6 n皇后_2009(包括回溯算法) 以上几个实验基本...
动态规划 # 问题 解决方案 困难 相关话题/想法 64 中等的 2020/12/11 基本dp 72 难的 2020/09/22 dp 字符串,类似于 376 HW2 123 难的 2020/08/16 日常练习,动态规划,还自带工整 486 中等的 2020/09/01 日常锻炼,...
第21部分 : 动态规划优化 第22部分:高级数据结构 第23部分 : 深度搜索应用 第24部分 : 广度搜索应用 第25部分 : 启发式搜索 第26部分:最大流 第27部分:最大流改进算法 第28部分:二分图最大匹配 第29部分:...
字符串、动态规划、回溯算法 To Do 11 中等 数组、双指针 12 中等 数学、字符串 13 简单 数学、字符串 14 简单 字符串 15 中等 数组、双指针 16 中等 数组、双指针 17 中等 字符串、回溯算法 18 中等 数组、哈希表、...
动态规划 To Do 6 中等 字符串 To Do 7 简单 数学 8 中等 数学;字符串 9 简单 数学 To Do 10 困难 字符串;动态规划;回溯算法 To Do 11 中等 数组;双指针 To Do 12 中等 数学;字符串 To Do 13 简单 数学;字符串 To Do...
2016-09-24_213732.wmv 2016-09-24_223543.wmv 数据结构1.pptx 2X1{SH5V_HSM`5JS[H]Z`JP.png 33XTI0U)]QTVK1MINJY0)F3.png 34MMEH64LMCA}H5G_RXKPGO.png 65]YTLJ{NP7ICB9{]%XK5J2.png ...30_动态规划(2).flv
leetcode 300题, 主要集中树, 回溯, 数组, 字符串, 贪心, 动态规划几个专题。 基本涉及所有分类。 下个目标是400题, 和复习一下之前的题目, 写一些比较深刻的题目的解析博客。 2019-08-17 至 2019-09-17 leetcode ...
蓝桥杯备赛:蓝桥杯备赛练习题与答案 目录: 00开发环境 01数据结构 02枚举和计数 03搜索 04动态规划 05贪心算法 06图论 07数论 08字符串 09线段树
贪心,回溯,动态规划 堆:一种完全二叉树,任意节点大于左右孩子(大顶堆) 树:二叉树,DFS,BFS 1 排序与查找 1 排序 平均,最坏,最好,空间复杂度,是否稳定 插入排序 O(n^2) O(n^2) O(n) O(1) 稳定 快速排序 O...
动态规划,背包问题 01背包问题:416. Partition Equal Subset Sum 最长回文:5. Longest Palindromic Substring - 字数组余数:523. Continuous Subarray Sum - 无重复字符的最长子串:3. Longest Substring ...
针对2019南开大学复试上级准备的动态规划相关例题,包括最长公共子序列问题.最大连续子序列和,数字三角形问题,最小回文划分,股票买卖,最短编辑距离,交叉字符串,Distinct Subsequence,01背包问题
数据结构 数组 字符串 队列 链表 双指针 栈 堆 树 二叉搜索树 字典树 线段树 并查集 哈希表 图基础算法 排序 回溯算法 分治算法 贪心算法 动态规划 Map 位运算 极小化极大抽象数学 随机 数学题目【2020-01-16】199....
动态规划 蓄水池算法:com.monkey.dp.Code01_Trap 编辑距离:com.monkey.dp.Code02_MinDistance 贴纸拼词:com.monkey.dp.Code03_MinStickers 要再看一遍 最长递增子序列:com.monkey.dp.Code04_LengthOfLIS 背包...
leetcode三角形打印 我的 LeetCode 刷题记录, 使用 Golang 加粗 代表需要重视 ...动态规划 2021/01/09 买卖股票的最佳时机 III (根据题解得出结果) 2020/10/20 最小路径和(64) 打家劫舍(198) 2020/
最长递增子序列(动态规划 + 二进制搜索以达到 O(n*log(n)))时间复杂度 53 号。 最大子阵列 可能 二分查找 二和二 剑指53 - IIoff 0~n-1中等级的数字 在旋转排序数组中搜索 _74. 搜索二维矩阵 队列 删除所有相邻的...
哈希表->字符串->栈与队列->树->回溯->贪心->动态规划->图论->高级数据结构,再从简单刷起,做了几个类型题目之后,再慢慢做中等题目、困难题目。 但我能设身处地的感受到:即使有这样一个整体规划,对于一位初学者...
leetcode 2 Leetcode-数据-结构-算法 第 1 部分:数据结构 01 阵列 02 链表 03 堆栈和队列 04 ...字符串 ...动态规划 16 贪心算法 17 数学 18 位操作 参考: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
leetcode卡 Leetcode 打卡日志 (Java) 个人打卡 leetcode 的记录,相信打卡的力量,在自律的路上遇到更好的自己。...第七周(动态规划/easy)2020-01-20 ~ 2020-01-26 春节,有点懈怠了。 第八周(栈/easy&medium)