9-爬楼梯

佚名 4年前 (2020-04-17) 算法 609人围观抢沙发百度已收录

题目如下：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

 1 /**
 2  * @author sunhongguang
 3  * @create 2020-04-17-12:10
 4  */
 5 public class Test4 {
 6     public static void main(String[] args) {
 7         int n = 45;
 8         int reslut = climbStairs(n);
 9         System.out.println(n+"阶台阶，一共有"+reslut+"种爬法");
10     }
11 
12     /**假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
13      * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
14      * 递归暴力求解
15      * @param n  台阶的个数
16      * @return   有多少中爬法
17      */
18     private static int climbStairs(int n) {
19         if(n <= 2) return n;
20         return climbStairs(n-1) + climbStairs(n-2);
21     }
22 
23     /**假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
24      * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
25      * 动态规划法
26      * @param n  台阶的个数
27      * @return   有多少中爬法
28      */
29     private static int climbStairs_1(int n) {
30         if(n == 1) return 1;
31         int[] dp = new int[n+1];
32         dp[1] = 1;
33         dp[2] = 2;
34         for(int i=3;i<=n;i++){
35             dp[i] = dp[i-1]+dp[i-2];
36         }
37         return dp[n];
38     }
39 }