70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

解法

1、n = 1，只有一种方法；
2、n = 2，有两种方法；
3、对于n > 2，则有 第一步爬1级台阶方法数 + 第一步爬2级台阶方法数，即：
                 f(n) = f(n-1) + f(n-2)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int climbStairs(int n, int *steps);

int main()
{
    int n = 10;
    int *steps = malloc(sizeof(int)*(n+1));
    memset(steps,0,sizeof(int)*(n+1));

    steps[n] = climbStairs(n,steps);
    printf("steps=%d\n",steps[n]);

    return 0;
}

int climbStairs(int n, int *steps)
{
    if(n == 1)
    {
        steps[n] = 1;
    }
    else if(n == 2)
    {
        steps[n] = 2;
    }
    else
    {
        if(steps[n-1] == 0)
        {
            steps[n-1] = climbStairs(n-1,steps);
        }
        if(steps[n-2] == 0)
        {
            steps[n-2] = climbStairs(n-2,steps);
        }
        steps[n] = steps[n-1] + steps[n-2];
    }

    return steps[n];
}