[Algorithm/Java][LeetCode] 70. Climbing Stairs

[LeetCode] 70. Climbinh Stairs

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

문제접근

처음에는 재귀를 이용해서 풀어보려고 해서 제출을 했지만 시간 초과가 나왔다.
그래서 DP 방식으로 풀어보았다.
DP 방식으로 풀기 위해서는 점화식?을 발견해야 한다. 뭔가 굉장히 어려워 보이지만 갑자기 감이 잡힌다.(규칙을 찾는 느낌?)
계단은 한번에 1칸 또는 2칸을 이동할 수 있다.
그러면 1번째 계단을 올라가려면 0번째에서 시작해야한다.
그리고 2번째 계단을 올라가기 위해서는 0번째거나 1번째 계단에서 시작해야한다.
또, 3번째 계단을 올라가기 위해서는 1번째거나 2번째 계단에서 시작해야한다.
여기서 n번째 계단을 오르기위해서는 n-1번째와 n-2번째 계단에서 시작해야하는것을 알 수 있다. 그러면 n-1번째 계단과 n-2번째 계단에 경우의 수를 합친 값이 n번째 계단에 오를 수 있는 경우의 수인것이다.

Code

class Solution {

    public int climbStairs(int n) {
        if(n<=2) return n;
        int[] step = new int[n+1];
        step[1] = 1; // 첫번째 계단은 방법 1개
        step[2] = 2; // 두번째 계단은 방법 2개
        for(int i = 3; i<=n; i++){
            // i번째 계단을 밟기 위해서는 i-1번째와 i-2번째 계단에서 와야한다.
            step[i] = step[i-1]+step[i-2];
        }
        return step[n];
    }
}

어려웠던 점 / 배운 점 / 느낀 점

점화식이라고 해서 어려워 보이지만 약간 규칙 찾는 느낌이다.
이런 문제는 백준에서도 몇번 봐서 어렵지 않게 접근할 수 있었다.
점화식을 사용하는 이유는 첫번째, 두번째 계단처럼 낮은 계단은 경우의 수를 구하기가 쉽지만 올라갈수록 경우의 수를 구하기가 어려워 지기때문에 규칙을 식으로 변환해서 풀기 위함이다.