OJ题：超级台阶 时间限制：1000 ms | 内存限制：65535 KB 难度：3 描述 有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？
注：规定从一级到一级有0种走法。
输入 输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40), 表示楼梯的级数。
输出 对于每个测试实例，请输出不同走法的数量。
一开始是用一个递推公式来求n阶台阶的走法 f(n) = f(n-1) +f(n-2) 从第4阶台阶开始，到达第n阶台阶总共有两种方法，一是从n-1阶台阶一次走一步，一是从n-2阶台阶一次走两步，而从n-2阶台阶先走一步再走一步到达的这种情况，实际上是从n-2阶台阶先走一步到达n-1阶再走一步，是属于第一种情况的 以此便可以得出上述递推式。 而n为1、2、3的情况直接求出便可。 这样便得出求走n阶台阶的方法的函数
#include <iostream>using namespace std;int f(int m){ if(i==1) return 0; if(i==2) return 1; if(i==3) return 2; return f(m-1)+f(m-2);}int main(){ int s;cin>>s; while(s--) { int m;cin>>m; cout<<f(m)<<endl; } return 0;}而在主函数调用时发现超时 仔细研究，觉得这个递推公式应该已经是最简单的了 虽然知道递归那里时间复杂度很高，但是发现每次调用f（）函数都要进行3次判断。 刚好发现了前面的操作可以合成为一个，于是把f（）函数改成
int f(int m){ if(m<=3) return m-1; return f(m-1)+f(m-2);}这样时间复杂度前面的系数可以变成1/3。 但是果然还是太天真了，还是递归了太多层才超的时 突然看到输入限制中，1<=m<=40 突然想到可以做一个数组，直接把每一个值的结果求出来，而因为前面的值已经求出来了，求当前第n阶的方法时，就只需要执行一次加法操作 a[n]=a[n-1]+a[n-2]; 果然 修改代码后AC了。
#include <iostream>using namespace std;int main(){ int s;cin>>s; int a[41]; a[1]=0;a[2]=1;a[3]=2; for(int j=4;j<=40;j++) a[j]=a[j-1]+a[j-2]; while(s--) { int m;cin>>m; cout<<a[m]<<endl; } }然后突然想到前两天刚开始做OJ做了一道题，一直超时，好像也可以这样求出来，于是立马回到那题
OJ题目：孪生素数问题 时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述 写一个程序，找出给出素数范围内的所有孪生素数的组数。一般来说，孪生素数就是指两个素数距离为2，近的不能再近的相邻素数。有些童鞋一看到题就开始写程序，不仔细看题，咱们为了遏制一下读题不认真仔细的童鞋，规定，两个素数相邻为1的也成为孪生素数。
输入 第一行给出N表示测试数据组数。(1<=N<100) 接下来组测试数据给出m，表示找出m之前的所有孪生素数。 (1<=m<1000000)
输出 每组测试数据输出占一行，该行为m范围内所有孪生素数组数
这个问题，一开始是从3开始，遍历所有不大于m的奇数，先判断这个奇数是不是质数，如果是再判断相邻的奇数是不是质数。 判断素数需要√n的时间复杂度，总共有n/2个数要判断。 虽然不能直接相乘，但是应该和√n*n的规模差不多 而m取到最大值的时候，显然就超时
当时做这题筛选法求质数也没做出来，反而一经上题启发 直接就开始写
#include <iostream>using namespace std;int a[1000001];bool PRime(int n){ if(n<=1) return false; for(int i=2;i*i<=n;i++) if(n%i==0) return false; return true;}int pri(int n){ if(prime(n)&&prime(n-2)) return 1; else return 0;}int main(){ a[1]=0;a[2]=0;a[3]=1; for(int i=4;i<1000001;i++) { a[i]=a[i-1]+pri(i); } int s;cin>>s; while(s--) { int n;cin>>n; cout<<a[n]<<endl; } return 0;}基本操作就变成了 a[i]=a[i-1]+pri(i);
两道题共同的地方就是，规模已知，然后第n次结果与前面的结果有关联，但是如果用递归或者蛮力，会很复杂，并且每次求一个不同的n，都要重新算。那么这样的话，建立一个等规模的数组，直接用前面的值按照公式去推后面的值，应该会要好一些。
新闻热点
疑难解答
