LeetCode - 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 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
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

• 직관적으로 for문을 중첩해서 모든 가능한 케이스를 검토해봄(가능한 케이스를 찾기전까지)

class Solution {
    public int climbStairs(int n) {

        // int[] numOfClimbWays=new int[n+1];
        int prePreWay = 1;
        int preWay = 1;

        int numOfWays = 0;
        for (int i = 2; i <= n; i++) {
            // numOfClimbWays[i]=numOfClimbWays[i-2]+numOfClimbWays[i-1];
            numOfWays = prePreWay + preWay;
            prePreWay = preWay;
            preWay = numOfWays;
        }
        // return numOfClimbWays[n];
        return numOfWays;
    }
}