동적계획법(Bottom up) in C++

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

#include <iostream>

using namespace std;

int n;
int dp[101];

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

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

동적 계획법이란?

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

ex)
7