계단오르기 [DP]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

 

풀이 

- 네트워크 선 자르기와 같은 방식으로 풀면 되는 문제

- 점화식을 구하면 f(n)=f(n-2)+f(n-1)

- 메모이제이션을 통해 하나씩 값을 기록해 가며 DFS함수를 사용한다

 

#include <stdio.h>
#include <algorithm>
int arr[101], n;

int DFS(int L){
    if(arr[L]>0) return arr[L];
    if(L==1 || L==2){
        return L;
    }else{
        return arr[L]=DFS(L-2)+DFS(L-1);
    }
}

int main(){
    scanf("%d", &n);
    printf("%d\n", DFS(n));
    return 0;
}