Difficulty: Easy

Related Topics: Dynamic Programming

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

  1. Input: n = 2
  2. Output: 2
  3. Explanation: There are two ways to climb to the top.
  4. 1. 1 step + 1 step
  5. 2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

  • 1 <= n <= 45

Solution

Language: Java

class Solution {
    int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        return dp(n);
    }

    // 定义：爬上 n 节台阶的不同方法
    private int dp(int n) {
        // 出口
        // 1. 一节台阶，只有一种方法，那就是一步爬上去
        if(n == 1) return 1;
        // 2. 两节台阶，有两种方法：
        //    1. 一步一步爬
        //    2. 两步直接跨上去
        if(n == 2) return 2;

        if(memo[n] != 0) return memo[n];

        // dp(n) = dp(n - 1) + dp(n - 2)
        // 要想爬上第 n 节台阶，只有两种方法
        // 1. 从 n - 1 节爬上来（一步）
        // 2. 从 n - 2 节跨上来（两步）
        return memo[n] = dp(n - 1) + dp(n - 2);
    }
}