동적계획법(Top Down) in C++

길이 n이 주어졌을때, 선을 자르는 방법의 수를 출력하는 코드

#include <iostream>

using namespace std;

int n;
int dp[101];
int DFS(int n) {
    if(dp[n] > 0) return dp[n];
    else {
        return dp[n] = DFS(n - 1) + DFS(n - 2);		// 메모이제이션
    }
}

int main() {
    freopen("input.txt", "rt", stdin);
    cin >> n;
    dp[1] = 1;
    dp[2] = 2;
    cout << DFS(n);
    return 0;
}

메모이제이션을 통해, 다음번에 동일한 계산을 반복하지 않도록한다.

• dp[1] : 선의 길이가 1일때, 자르는 경우의 수
• dp[2] : 선의 길이가 2일때, 자르는 경우의 수
• dp[n] : 선의 길이가 n일때, 자르는 경우의 수

동적 계획법이란?

• 문제의 크기를 아주 작은 단위로 축소한 뒤, 그 작은 단위에서의 답을 구하고, 살짝 더 큰 단위의 문제를 푸는 형식이다.
• 이 과정을 반복해서 나간다.
• 즉 점화식의 방식이라고 볼 수 있다.

ex)
7