[LeetCode- Ch8. 동적계획법] 2. 계단 오르기 #

https://leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

 

1칸이나 2칸씩 오를 수 있다.

0칸 -> 경우의 수 0

1칸 -> 경우의 수 1

2칸 -> 경우의 수 2

....

n칸 -> n-1칸의 경우의 수 + n-2칸의 경우의 수

 

class Solution {
    public int climbStairs(int n) {
        //계단은 1칸이나 2칸씩 오를 수 있다.
        //꼭대기까지 올라가는 경우의 수는 몇가지가 존재하는가
        
        //2 -> 1+1, 2
        int answer=0;
        
        //1
        //0일때 ->1
        //1일때 ->0
        //: 1
        
        //2
        //0일때 -> 1과 2
        //1일때 -> 1
        //2일때 -> 0
        //: 1,1
        //: 2
        
        //2인경우 1 -> 2
        
        //3
        //0일때 -> 1과 2
        //1일때 -> 1과 2
        //2일때 -> 1
        //3일때 -> 0
        //: 1,1,1
        //: 2,1
        //: 1,2
        //2인경우 2 -> 3
        
        //4
        //0일때 -> 1과 2
        //1일때 -> 1과 2
        //2일때 -> 1과 2
        //3일때 -> 1
        //4일때 -> 0
        //: 1,1,1,1 
        //: 2,2,0 
        
        int[] arr= new int[n+1];
        //0, 1, 2, 3
        //0에서 가능한 경우의 수
        //1에서 가능한 경우의 수 =0에서 가능한 경우의 수
        //2에서 가능한 경우의 수 =0에서 가능한 경우의 수 + 1에서 가능한 경우의 수
        
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;                
        }else if(n==2){
            return 2;
        }
        
        arr[0]=0;
        arr[1]=1;
        arr[2]=2;
        
        for(int i=3;i<=n;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        
        
        
        return arr[n];
    }
}