每天一题LeetCode【第51天】

T70. Climbing Stairs【Easy】

题目

你要爬楼梯。你面对的是一个 n 步可以走上去的楼梯。

你每次可以走一步或者两步，那么你有几种不同的方式可以爬上去吗？

注意：给出的 n 是一个正数

思路

简单说一个例子：

走到 第53阶 可能有两种情况：
① 从 第52阶 一步走到 ② 从 第51阶 两步走到

所以 到53阶方式数 = 到52阶方式数 + 到51阶方式数

代码

代码取自 Top Solution，稍作注释

public int climbStairs(int n) {
    // 边界处理
    if(n == 0 || n == 1 || n == 2){return n;}
    // 设置一步和两步的初值
    int[] mem = new int[n];
    mem[0] = 1;
    mem[1] = 2;
    // 后一个等于前两个之和，看“思路”
    for(int i = 2; i < n; i++){
        mem[i] = mem[i-1] + mem[i-2];
    }
    return mem[n-1];
  }