계단 오르기

문제

코드

Top-Down 방식

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// 참고 ) bottom - up 이 DP의 의미가 더 있다.

int dy[101]; // 메모이제이션용
int DFS(int n)
{
    if (n == 1 || n == 2)
        dy[n] = n;
    if (dy[n] > 0)
        return dy[n];
    else
        return DFS(n - 2) + DFS(n - 1);
}
int main(int argc, char const *argv[])
{

    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    // TOP-DOWN 방식
    cout << DFS(n) << '\n';

    return 0;
}

DFS에서 메모이제이션을 활용하게 된다면 중복연산을 피할 수 있으므로 속도가 향상된다.

BOTTOM -UP방식

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

// 참고 ) bottom - up 이 DP의 의미가 더 있다.

int dy[101];

 
 int main(int argc, char const *argv[])

    dy[1] = 1;
    dy[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        dy[i] = dy[i - 2] + dy[i - 1];
    }

    cout << dy[n] << endl;
    
    
    return 0;
}

• 1번째 계단 오르는 경우의 수 : 1가지
• 2번째 계단 오르는 경우의 수 : 2가지
• 3번째 계단 경우의 수 : 3가지 ( 1 + 2 )
  1번째 계단 또는 2번째 계단에서밖에 오를 수 없다.
  
• 4번째 계단 : 5가지 ( 2 + 3 )
  2번째 계단 또는 3번째 계단에서밖에 오를 수 없다.

점화식 : f(n) = f(n -2) + f(n -1)