(LeetCode) 70. Climbing Stairs

The link : leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

문제는 다음과 같다. 

1. 한 칸, 혹은 한 번에 두 칸씩만 오를 수 있는 계단이 있다.

2. 정해진 N번째 계단까지 가기 위한 가지수를 출력하라.

 

타임리밋이 나지 않도록 풀기 위해서  동적할당(Dynamic Programming, Memoization)을 활용했다.

 

class Solution {
public:
    int arr[46];
    
    int dfs(int n){
        if(n==0) return 1;
        else if(n<0) return 0;
        else if(arr[n]) return arr[n];
        return arr[n] = dfs(n-1) + dfs(n-2);
    }  

    int climbStairs(int n) {
       return dfs(n);
    }
};