Chinaunix首页 | 论坛 | 博客
  • 博客访问: 874261
  • 博文数量: 376
  • 博客积分: 154
  • 博客等级: 入伍新兵
  • 技术积分: 1558
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-13 08:42
文章分类

全部博文(376)

文章存档

2014年(11)

2013年(88)

2012年(260)

2011年(17)

分类:

2012-10-08 08:29:57

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

一个简单的动态规划题。
使用数组ways[i]表示第i个台阶有ways[i]种方法。
那么 ways[n] = ways[n-2] + ways[n-1];


点击(此处)折叠或打开

  1. /*
  2.  * =====================================================================================
  3.  *
  4.  * Filename: steps.c
  5.  *
  6.  * Description:
  7.  *
  8.  * Version: 1.0
  9.  * Created: 10/03/2012 02:25:55 PM
  10.  * Revision: none
  11.  * Compiler: gcc
  12.  *
  13.  * Author: YOUR NAME (),
  14.  * Organization:
  15.  *
  16.  * =====================================================================================
  17.  */
  18. #include <stdlib.h>
  19. #include <stdio.h>

  20. /*
  21.  * === FUNCTION ======================================================================
  22.  * Name: main
  23.  * Description:
  24.  * =====================================================================================
  25.  */
  26.     int
  27. main ( int argc, char *argv[] )
  28. {
  29.     int steps = 10;
  30.     int ways[10000] ={0};
  31.     ways[0] = 1;
  32.     int i = 0;
  33.     for(;i<=steps;i++){
  34.         ways[1+i] += ways[i];
  35.         ways[2+i] += ways[i];
  36.     }
  37.     printf ( "%d\n", ways[steps] );
  38.     return EXIT_SUCCESS;
  39. }                /* ---------- end of function main ---------- */


阅读(302) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~