【赛码网刷题】动态规划之上台阶
时间限制： 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
}
}
其中，这个赛码网要特别注意输入和输出数据
读取一行输入
read_line()
将读取至多1024个字符，当还未达到1024个时如果遇到回车或结束符，提前结束。
读取多行最简单的办法是
while((line = read_line()) != '')
所以上面的代码，
var n = read_line();
表示读取第一行数据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]))
}
}
}
while((line = read_line()) != ‘’)表示读取多行。
因为通过read_line()读取的数据都是字符串，所以在这个题上面我们需要转化为整型。我们将读取的第一行数据放到了line里面，再强制类型转换，把它压入数组中，接着我们判断一下数组的长度是不是我们输入的长度，如果是的话，就不需要再读取数据了，如果不是的话，就需要接着进行循环，需要再接着读取数据，进行强制类型转换，压入到数组中。此时我们的数组中存储的都是m的值，所以需要循环遍历数组，将这些数据进行处理。
其次，以上代码主体是判断楼梯级数整数m，共有几种走法，也就是fun函数，我们可以列出几个台阶，找找规律
| 阶数 | 走法数 |
|---|---|
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| … | … |
| 可以看出上面就是一个斐波那契数列，可以总结出 f(n）=f(n-1）+f(n-2)的递推关系式，所以就有上述写法。 |