【LeeCode】爬楼梯

【题目描述】

假设你正在爬楼梯。需要 ​​n​​ 阶你才能到达楼顶。

每次你可以爬 ​​1​​​ 或 ​​2​​ 个台阶。你有多少种不同的方法可以爬到楼顶呢？

【示例】

【代码1 -- 简单】

import javax.swing.plaf.IconUIResource;
import java.util.*;

/**
* 有效的括号
*
* https://leetcode.cn/problems/valid-parentheses/?favorite=2cktkvj
*/
public class Solution {
public static void main(String[] args) {
int num = 45;
System.out.println(climbStairs(num));
    }


// 方案1： 会超时  因为递归的计算量比较大
public static int climbStairs(int n) {
// 因为 n - 2 当n==2是 此时输入为0
if(n == 1 || n == 0 ){
return 1;
        } else {
return climbStairs(n - 1) + climbStairs( n - 2);
        }
    }
}

【代码2 -- 推荐】

import javax.swing.plaf.IconUIResource;
import java.util.*;

/**
* 有效的括号
*
* https://leetcode.cn/problems/valid-parentheses/?favorite=2cktkvj
*/
public class Solution {
public static void main(String[] args) {
int num = 45;

System.out.println(climbStairs2(num));
    }

// 方案2: 基于数组
private static int climbStairs2(int num) {
int[] dp = new int[num + 1];  // 因为 num+1的位置是保留最后结果的
dp[0] = 1;
dp[1] = 1;

for(int i = 2; i <= num; i++){
dp[i] = dp[i - 1] + dp[i - 2];
        }
return dp[num];   // 最后一个结果保留的下标是num
    }
}

​​https://leetcode.cn/problems/climbing-stairs/?favorite=2cktkvj​​