70. Climbing Stairs

문제

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 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

링크: https://leetcode.com/problems/climbing-stairs/description/

Solution

class Solution {
    public int climbStairs(int n) {
        if(n == 0 || n ==1) return 1;

        return climbStairs(n-1) + climbStairs(n-2);
    }
}

회고

피보나치 수열로 해결할 수 있는 다이나믹 프로그래밍 문제이다. 계단 단위는 1 또는 2이다. n번 째 계단을 오르는 경우의 수는 (n-2)번 째 오르는 경우에서 2 계단을 오르거나 (n-1)번 째 계단에서 1 계단을 오르는 경우이다.

따라서

climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)