9.1 有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一个方法，计算小孩有多少种上楼梯的方法。

解法：

我们可以采用自上而下的方式来解决这个问题。小孩上楼梯的最后一步，也就是抵达第n阶的那一步，可能走1阶、2阶或3阶。也就是说，最后一步可能是从第n-1阶往上走1阶、从n-2阶往上走2阶，或从第n-3阶往上走3阶。因此，抵达最后一阶的走法，其实就是抵达这最后三阶的方式的总和。

 

递归的方法实现：

int countWaysD(int n){    if(n<0)        return 0;    else if(n==0)        return 1;    else    {        return countWaysD(n-1)+countWaysD(n-2)+countWaysD(n-3);    }}

使用3个临时变量的方法：

int countWays(int n){    if(n<0)        return 0;    if(n==0)        return 1;    int first=0,second=0,third=1;    int i=1;    int ret;    while(i<=n)    {        ret=first+second+third;        first=second;        second=third;        third=ret;        i++;    }    return ret;}

使用dp的方法，需要一个数组来记录前面已经求出的值。

int countWaysDP(int n,int dp[]){    if(n<0)        return 0;    if(n==0)        return 1;    if(dp[n]>0)        return dp[n];    else        dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp);    return dp[n];}

C++实现代码：

#include
     
      #include
      
       #include
       
        using namespace std;const int MAX=1000;int countWaysD(int n){    if(n<0)        return 0;    else if(n==0)        return 1;    else    {        return countWaysD(n-1)+countWaysD(n-2)+countWaysD(n-3);    }}int countWays(int n){    if(n<0)        return 0;    if(n==0)        return 1;    int first=0,second=0,third=1;    int i=1;    int ret;    while(i<=n)    {        ret=first+second+third;        first=second;        second=third;        third=ret;        i++;    }    return ret;}int countWaysDP(int n,int dp[]){    if(n<0)        return 0;    if(n==0)        return 1;    if(dp[n]>0)        return dp[n];    else        dp[n]=countWaysDP(n-1,dp)+countWaysDP(n-2,dp)+countWaysDP(n-3,dp);    return dp[n];}int main(){    int dp[MAX]={
   0};    for(int i=1; i<10; i++)        cout<
        
         <