1，假设有n个台阶的楼梯，一个人要上这个楼梯，他每次可以走1个台阶或者2个台阶，问走上这个楼梯的走法总共有多少种？
解答：这个题目可以从最简单的办法逐步掌握其规律，比如走上1个台阶总共只有1种走法，而走上2个台阶有两种走法（一种直接走2步，一种走2个一步），我们知道要走上第i个台阶，要么是从第i-1个台阶走一小步到的，要么是从第i-2个台阶走1大步。用F(i)表示走上第i个台阶的走法总数，那么F(1)=1，F(2)=2，那么F(i)是依赖于F(i-1)和F(i-2)的，其中 2<i<=n, 我们很容易知道 F(i)=F(i-1)+F(i-2)。也就是说我们最终问题的解为F(n)=F(n-1)+F(n-2)，F(1)=1，F(2)=2. 了解斐波那契数列的人就知道这明显就是一个斐波那契数列。
根据 我们可以通过一些数学方法求得其通项公式。我们当然也可以通过方程递归的求解问题：
int Step(int n)
{
if(n==1)
else if (n==2)return 1;
return 2;else
return Step(n-1)+Step(n-2)
}
这个过程的时间复杂度为O(2^n)，我们可以用循环递推来改变这个时间代价
int step(int n)
{
int *a=new int[n];a[0]=1;a[1]=2;for(i=2;i<n;i++){
a[i]=a[i-1]+a[i-2];
}int res=a[n-1];delete [] a;return res;
}
2，还是上面的问题，假设这个人在上楼的过程中可以退回1个台阶，而且整个上楼过程只能后退一次，问走上这个楼梯有多少种走法？
解答：这个题目的分析思路和上面一样，因为后退一步只发生了一次，我们可以假设它发生在第1, 2, ..., n个台阶，然后看其影响。我们的分析乳如下：
假设退后一步发生在第1个台阶： F(1)=1, F(2)=2, F(n)=F(n-1)+F(n-2) 。对结果没有影响
假设退后一步发生在第2个台阶： F(1)=1+F(2) , F(2)=2, F(n)=F(n-1)+F(n-2) 。 因为到达第1个台阶可以从第2个台阶退回，所以我们只需要在原有F(n)的结果上加上F(2)的取值，就是问题的解。
假设后退一步发生在第3个台阶：F(1)=1, F(2)=2+F(3), F(n)= F(n-1)+F(n-2). 因为到达第2个台阶可以从第3个台阶退回，所以我们只需要在原有F(n)的结果上加上F(3)的取值，就是问题的解。
.......
假设后退一步发生在第n个台阶： F(1)=1, F(2)=2, F(n-1)= F(n-1)+F(n-2)+F(n), F(n)= F(n-1)+F(n-2). 因为到达第n-1个台阶可以从第n个台阶退回，所以我们只需要在原有F(n)的结果上加上F(3)的取值，就是问题的解。
所以还用上面第一题的程序求出F(2),.....,F(n)，然后问题的解为：F(n)+F(2)+.....+F(n)
红色部分就是由于退回一步对问题的解增加的步数。
3，现在有一个双向的环形链表，包含n个节点，编号从0,1,......n-1，问从0节点开始走m步回到0节点，不同的走法有多少种？（每一步的定义为从第i个节点出发，要么走向i-1，要么走向i+1，为一步(0=<i<=n-1)，当 i-1=-1 时，代表走向的是n-1这个点，当 i+1=n 时，代表走向的是0这个节点）
解答：这个问题我们还是递归地来考虑，我们知道在到达第0个点之前，我们要么在第1个点，要么在第n-1个点，假设Q(i,j)表示我们从0点开始走了j步到达第i个点的走法总数，那么很容易得到：
那么原问题就是要求Q(0,m)。而且初始情况为（也即递归结束的条件），从0点走1步时，有：Q(i,j)=Q（i-1 mod n,j-1)+Q(i+1 mod n,j-1)Q(0,1)=0;Q(1,1)=1;Q(2,1)=0;....Q(n-2,1)=0;Q(n-1,1)=1.那么这个问题就可以递归地求解如下：
int step(int i,int j,int n) //递归版本
{
if(n==0 or n==1) //error detect
return 0;
if(j==1){
if(i==1 || i==n-1)
return 1;else
return 0;
} else
return step((i-1) % n,j-1,n)+step((i+1) % n,j-1);
}
问题的解就为step(0,m)。这个递归算法的复杂度同样为O(2^m)，我们同样可以通过空间换时间，递推算法来优化如下，优化的时间代价为O(m*n)：
int step(int i,int j,int n,int m) //非递归版本{
//动态生成二维数组
int **Q=new int*[n];for(int i=0;i<n;i++){
Q[i]=new int[m+1]; // 0到m
}
if(n==0 or n==1) //error detectreturn 0;//初始化for(int i=0;i<n;i++){
if(i==1 || i==n-1){
Q[i][1]=1;
}else
Q[i][1]=0;
}//循环求解for(int j=2;j<=m;j++){
for(int i=0;i<n;i++){
Q[i][j]=Q[(i-1)%n][j-1]+Q[(i+1)%n][j-1];
}
}int res=Q[0][m];delete [] Q;return res;}