微软面试100题(27):跳台阶问题

27.跳台阶问题：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共 有多少总跳法，并分析算法的时间复杂度。

一个简单的动态规划题。

使用数组ways[i]表示第i个台阶有ways[i]种方法。

那么 ways[n] = ways[n-2] + ways[n-1];

/*
 * =====================================================================================
 *
 *       Filename:  steps.c
 *
 *    Description:
 *
 *        Version:  1.0
 *        Created:  10/03/2012 02:25:55 PM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (),
 *   Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>
#include <stdio.h>

/*
 * ===  FUNCTION  ======================================================================
 *         Name:  main
 *  Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int steps = 10;
    int ways[10000] ={0};
    ways[0] = 1;
    int i = 0;
    for(;i<=steps;i++){
        ways[1+i] += ways[i];
        ways[2+i] += ways[i];
    }
    printf ( "%d\n", ways[steps] );
    return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */