【赛码网刷题】动态规划之上台阶

时间限制： 3000MS
内存限制： 589824KB

题目描述：

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？

注：规定从一级到一级有0种走法。
输入描述

输入数据首先包含一个整数n(1<=n<=100)，表示测试实例的个数，然后是n行数据，每行包含一个整数m，（1<=m<=40), 表示楼梯的级数。

输出描述：

对于每个测试实例，请输出不同走法的数量。

样例输入

2 2 3

样例输出

1 2

代码如下：

var n = read_line(); //表示实例个数
var arr = [];
var m; //m表示楼梯级数
var line;
while((line = read_line()) != ''){
  arr.push(parseInt(line))
  if(arr.length === parseInt(n)){
    for(let i = 0;i<n;i++){
      console.log(fun(arr[i]))
    }
  }
}
//判断楼梯级数整数m，共有几种走法
function fun(m){
  if(m>=4){
    return fun(m-1)+fun(m-2);
  }else if(m === 3){
    return 2;
  }else if(m === 2){
    return 1;
  }else if( m===1){
    return 0
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

其中，这个赛码网要特别注意输入和输出数据
读取一行输入

read_line()
1

将读取至多1024个字符，当还未达到1024个时如果遇到回车或结束符，提前结束。
读取多行最简单的办法是

while((line = read_line()) != '')
1

所以上面的代码，

var n = read_line(); 
1

表示读取第一行数据n，n表示实例个数。
再定义一个数组用来存储n个楼梯级数
m表示楼梯级数。
定义一个line用来存放一行的数据。
以上是前4行的含义。

while((line = read_line()) != ''){
  arr.push(parseInt(line))
  if(arr.length === parseInt(n)){
    for(let i = 0;i<n;i++){
      console.log(fun(arr[i]))
    }
  }
}
1
2
3
4
5
6
7
8

while((line = read_line()) != ‘’)表示读取多行。
因为通过read_line()读取的数据都是字符串，所以在这个题上面我们需要转化为整型。我们将读取的第一行数据放到了line里面，再强制类型转换，把它压入数组中，接着我们判断一下数组的长度是不是我们输入的长度，如果是的话，就不需要再读取数据了，如果不是的话，就需要接着进行循环，需要再接着读取数据，进行强制类型转换，压入到数组中。此时我们的数组中存储的都是m的值，所以需要循环遍历数组，将这些数据进行处理。

其次，以上代码主体是判断楼梯级数整数m，共有几种走法，也就是fun函数，我们可以列出几个台阶，找找规律