爬楼梯
程序员文章站
2022-06-21 13:41:40
爬楼梯题目来源:爬楼梯题目表述:假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数。分析:根据题目,可以先列个表当n=3时,可以看成 一级台阶时上两步+二级台阶时上1步,及Count(3)=count(2)+count(1)。当n=4时,可以看成 二级台阶时上两步+三级台阶时上1步,及Count(4)=count(3)+count(2)。…即可以得出递推关系式:代码实现import...
爬楼梯
题目来源:爬楼梯
题目表述:
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
分析:
根据题目,可以先列个表
当n=3时,可以看成 一级台阶时上两步+二级台阶时上1步,及Count(3)=count(2)+count(1)。
当n=4时,可以看成 二级台阶时上两步+三级台阶时上1步,及Count(4)=count(3)+count(2)。
…
即可以得出递推关系式:
代码实现
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner =new Scanner(System.in);
while(scanner.hasNext()) {
int n = scanner.nextInt();
System.out.println(Count(n));
}
}
public static int Count(int n) {
int [] dp =new int [n+1];
if(n<3) {
return n;
}else {
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3;i<dp.length;i++) {
dp[i]=dp[i-1]+dp[i-2];
}
}
return dp[dp.length-1];
}
}
本文地址:https://blog.csdn.net/weixin_45282433/article/details/112251270
上一篇: 树形数据的工具类