[LeetCode]70. Climbing Stairs (Fibonacci sequence)

Climbing Stairs

link : https://leetcode.com/problems/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

n개의 계단이 있을때 오를 수 있는 경우의 수를 계산
조건 : 계단은 한칸 혹은 두칸씩 오를 수 있다.

풀이 포인트
1과 2를 조합하여 n을 만들 수 있는 경우의 수를 구하면 된다.

n=1
(1,1)

n=2 
(1,1) (2)

n=3
(1,1,1) (1,2) (2,1)

n=4
(1,1,1,1) (1,1,2) (1,2,1) (2,1,1)

여기까지 계산을 했을 때 어느정도 패턴이 보였다

n이 4일때 내가 만약 한칸을 올라가면 남은칸은 3칸이므로 남은 경우의 수는 n=3일때와 같으며
내가 두칸을 올라가면 n=2일때 올라갈 수 있는 경우의 수가 남는다

n개의 계단에서 오를 수 있는 방법의 개수를 k(n)이라 했을때

k(n) = k(n-1) + k(n-2)인 수식이 나온다. 

즉, 피보나치 수열을 만들면 된다.

class Solution {
    public int climbStairs(int n) {
        int cntBefore=1;
        int cntAfter= 1;  

        if(n ==1) return 1;
        if(n ==2) return 2; //1과 2의 경우 n-1, n-2가 나올수 없으므로 따로 저장

        if(n > 2){
           for(int i=0;i<n-1;i++){ //for문 돌려보니 n-1인 경우에 완성이 됨
               int temp = cntAfter; //n-1값 저장
               cntAfter = temp + cntBefore; //n-1과 n-2 더해줌
               cntBefore = temp; // n-1을 n-2를 저장하던 곳에 넣어줌
           }  
        }

        return cntAfter;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Climbing Stairs.

Memory Usage: 35.6 MB, less than 71.64% of Java online submissions for Climbing Stairs.

피보나치 수열이 나온다는 점을 찾은거랑 피보나치 수열을 직접 구현했는데 가장 빠른경우라서 기부니가 좋습니다.

class Solution {
public int climbStairs(int n) {
int f[] = new int[n + 1];

f[0] = 1; 
f[1] = 1; 

for (int i = 2; i <= n; i++) { 

f[i] = f[i - 1] + f[i - 2]; n.
} 

return f[n]; 

}

다른 사람이 만든건데 아예 배열에 저장해서 더했나보다.

왜 배열 만들 생각을 못했을까... 멍청이...