上台阶问题
问题描述
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或者二级，要走上M级，共有多少走法？其中M取值范围为1~100，结果值需要Mod 1000000007的值。
例如 输入 3
输出 2
输入 100
输出687995182
解决思路
刚开始看到这道题的时候也没看明白，后来在网上找了一下，看到了f(n)=f(n-1)+f(n-2)这个方法也就是斐波那契数列，也就是到n这个台阶的走法等于到n-1个台阶的走法个数加上到n-2个台阶的走法格式，比如n=3时的走法就等于走到第一个台阶的方法个数加上走到第2个台阶的方法个数（注意，刚开始你在第一级，不是在第0级）。
我们可以采用动态规划的方法求解。
首先定义一个数组来保存计算的数值
int[] data=new int[n+1];
定义一个循环来对该数列进行赋值，因为f(n)=f(n-1)+f(n-2)，所以我们只需要知道n=2和n=3的计算数值就可以计算出后面的方法个数
for(int i=1;i<=n;i++) {
if(i==1) {
data[1]=0;
}
else if(i==2) {
data[2]=1;
}
else if(i==3) {
data[3]=2;
}
else {
data[i]=(data[i-1]+data[i-2])%1000000007;
}
}
定义一个方法将上面的代码写入并返回data[n]的数值。然后在主函数中直接调用输出即可。
完整代码如下：
import java.util.*;
public class ShangLouTi {
static Scanner cin=new Scanner(System.in);
static int n=cin.nextInt();//台阶数
public static void main(String[] args) {
System.out.println(zoufa(n));
}
public static int zoufa(int n) {
int[] data=new int[n+1];
for(int i=1;i<=n;i++) {
if(i==1) {
data[1]=0;
}
else if(i==2) {
data[2]=1;
}
else if(i==3) {
data[3]=2;
}
else {
data[i]=(data[i-1]+data[i-2])%1000000007;
}
}
return data[n];
}
}
