# 동적 계획법

상태가 같으면 남은 선택도 같은지 먼저 따져 봅니다. 이를 만족해야 여러 경로로 도달한 상태를 하나로 합치고, 최소 비용이나 경우의 수를 재사용할 수 있습니다.

이어지는 예제는 상태에 무엇을 남겨야 다음 선택을 결정할 수 있는지 보여 줍니다.

## 2차원 DP: 격자 경로 세기

격자에서 오른쪽 또는 아래로만 이동해 `(0, 0)`에서 `(h - 1, w - 1)`까지 가는 경우의 수를 구해 봅시다. `h, w >= 1`이며 장애물이 있는 칸은 지나갈 수 없습니다.

상태는 자연스럽게 잡을 수 있습니다.

```text
dp[r][c] = (0, 0)에서 (r, c)까지 오는 경로 수
```

현재 칸에 도착하는 방법은 위에서 내려오거나 왼쪽에서 오는 것뿐입니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp
vector<vector<long long>> dp(h, vector<long long>(w, 0));
dp[0][0] = 1;

for (int r = 0; r < h; ++r) {
    for (int c = 0; c < w; ++c) {
        if (blocked[r][c]) {
            dp[r][c] = 0;
            continue;
        }
        if (r > 0) dp[r][c] += dp[r - 1][c];
        if (c > 0) dp[r][c] += dp[r][c - 1];
    }
}
```

이 문제에서는 위쪽 행과 왼쪽 칸이 먼저 계산되어야 하므로 `r`을 위에서 아래로, `c`를 왼쪽에서 오른쪽으로 훑습니다. 장애물은 경로 수 0, 출발점은 막혀 있지 않을 때 1입니다. 격자가 커지면 경로 수가 정수 범위를 넘으므로 문제에서 정한 나머지 조건이나 수의 범위를 반영해야 합니다.

## 최소 동전 개수: 그리디가 깨질 때

동전 단위가 `{1, 3, 4}`이고 6원을 만들 때, 가장 큰 동전부터 고르면 `4 + 1 + 1`로 3개가 됩니다. 하지만 최적해는 `3 + 3`으로 2개입니다. 이런 문제는 보통 DP로 접근합니다.

```text
dp[x] = 금액 x를 만드는 데 필요한 최소 동전 개수
dp[0] = 0
dp[x] = min(dp[x - coin] + 1)
```

```cpp
const int INF = 1e9;
vector<int> dp(target + 1, INF);
dp[0] = 0;

for (int x = 1; x <= target; ++x) {
    for (int coin : coins) {
        if (x >= coin) {
            dp[x] = min(dp[x], dp[x - coin] + 1);
        }
    }
}
```

동전 단위는 양수, `0 <= target < INF`이며 배열이 메모리에 들어가는 크기입니다. 도달할 수 없는 금액은 `INF`로 남습니다. `dp[target] == INF`이면 답이 없는 경우이며, 이를 큰 동전 개수로 출력해서는 안 됩니다. 위 코드는 금액 순서로 모두 계산하지만, 재귀로 필요한 금액만 계산하고 저장하는 메모이제이션도 가능합니다. 두 방식 모두 한 상태를 다시 풀지 않는다는 점은 같습니다.

## 0/1 배낭 DP

![무게 2 가치 3인 물건 하나의 DP 셀 갱신. 역방향은 아직 0인 작은 용량을 읽어 답 3을 얻지만, 정방향은 이번 물건으로 만든 dp[2]=3을 다시 읽어 잘못된 답 6을 만듭니다.](lesson-assets/concept-trace.svg)

[그림 크게 보기](https://git.readiz.com/h-contest-lesson/lessons/dynamic-programming/lesson-assets/concept-trace.svg)

각 행은 한 칸을 갱신한 직후의 배열입니다. 화살표의 시작은 읽는 칸, 끝은 갱신하는 칸입니다. 같은 `dp[2]`를 읽어도 역방향에서는 이전 물건까지의 값 0, 정방향에서는 이번 물건을 이미 넣은 값 3이라는 차이를 확인하세요.

용량은 음이 아닌 정수, 물건 무게는 양의 정수이며 가치 합은 사용 자료형 범위 안입니다. 각 물건을 한 번씩만 골라 무게 제한 안에서 가치 합을 최대화합니다. 앞 `i`개 물건을 본 답을 `dp[i][w]`라 두면, 현재 물건을 건너뛴 `dp[i - 1][w]`와 고른 `dp[i - 1][w - weight] + value` 중 큰 값이 답입니다.

이전 행만 필요하므로 배열 하나로 줄일 수 있습니다. 아직 현재 물건이 반영되지 않은 칸을 읽도록 용량을 큰 쪽부터 갱신합니다.

```cpp
vector<int> dp(capacity + 1, 0);

for (auto item : items) {
    for (int w = capacity; w >= item.weight; --w) {
        dp[w] = max(dp[w], dp[w - item.weight] + item.value);
    }
}
```

무게 2, 가치 3인 물건 하나와 용량 4를 생각해 봅시다. 용량을 올리며 갱신하면 `dp[2] = 3`을 같은 물건에서 다시 읽어 `dp[4] = 6`으로 만듭니다. 이는 같은 물건을 두 번 고른 결과입니다. 내림차순이면 `dp[4]`를 계산할 때 `dp[2]`는 아직 0이어서 답 3을 얻습니다.

같은 물건을 여러 번 쓸 수 있는 문제라면 반대로 오름차순으로 갱신합니다.

## LIS: 가장 긴 증가 부분수열

수열에서 순서를 유지하며 증가하는 원소를 골라 가장 긴 길이를 구하는 문제입니다.

가장 직관적인 상태는 다음과 같습니다.

```text
dp[i] = i번째 원소를 마지막으로 하는 LIS 길이
```

`i`보다 앞에 있고 `a[j] < a[i]`인 원소 뒤에 `a[i]`를 붙일 수 있습니다.

```cpp
vector<int> dp(n, 1);

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < i; ++j) {
        if (a[j] < a[i]) {
            dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

int answer = dp.empty() ? 0 : *max_element(dp.begin(), dp.end());
```

시간 복잡도는 `O(n^2)`입니다. `n`이 크면 `tails[len - 1] = 길이가 len인 증가 부분수열의 가능한 마지막 값 중 최솟값`을 유지해 `O(n log n)`으로 줄일 수 있습니다.

```cpp
vector<int> tails;

for (int x : a) {
    auto it = lower_bound(tails.begin(), tails.end(), x);
    if (it == tails.end()) {
        tails.push_back(x);
    } else {
        *it = x;
    }
}

int answer = (int)tails.size();
```

`tails[len - 1]`은 길이가 `len`인 증가 부분 수열의 가능한 최소 끝값입니다. 각 칸을 만든 부분 수열은 서로 다를 수 있어 `tails` 전체가 실제 LIS인 것은 아닙니다.

## 트리 DP

트리에서는 부모를 하나 정하면 자식 부분트리들이 서로 독립이 됩니다. 이 구조를 이용해 각 정점의 부분트리 답을 계산합니다.

대표 예시로, 인접한 두 정점을 동시에 고를 수 없을 때 고른 정점 가중치 합의 최댓값을 구해 봅시다.

```text
dp[u][0] = u를 고르지 않았을 때 u의 부분트리 최대값
dp[u][1] = u를 골랐을 때 u의 부분트리 최대값
```

`u`를 고르면 자식은 고를 수 없습니다. `u`를 고르지 않으면 자식은 고르거나 고르지 않거나 더 좋은 쪽을 택합니다.

```cpp
void dfs(int u, int parent) {
    dp[u][0] = 0;
    dp[u][1] = weight[u];

    for (int v : graph[u]) {
        if (v == parent) continue;
        dfs(v, u);

        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}
```

`graph`는 무방향 트리의 인접 목록, `weight[u]`는 정점 가중치입니다. `dfs(root, -1)` 뒤 답은 `max(dp[root][0], dp[root][1])`입니다. 가중치 합이 클 수 있으면 `dp`를 `long long`으로 둡니다. 일자 트리에서는 재귀 깊이가 정점 수까지 늘어납니다.

방문한 집합까지 상태에 필요하다면 [TSP의 비트마스크 DP](https://h.readiz.com/learn/tsp-hamiltonian)로 이어집니다.

## 로컬 연습: 각 물건을 한 번만 고르는 배낭

물건을 각각 최대 한 번 골라 총 무게가 W 이하일 때의 최대 가치 합을 구하세요. 아무 물건도 고르지 않아도 됩니다.

**입력:** N W 뒤 N줄의 무게와 가치. 1 <= N <= 100, 0 <= W <= 10000, 1 <= 무게 <= 10000, 0 <= 가치 <= 10^9입니다.

**출력:** 최대 가치 합을 출력합니다.

### 예시

```text exercise=dynamic-programming role=input
4 7
3 4
4 5
2 3
5 7
```

```text exercise=dynamic-programming role=output
10
```

**확인 방법:** 무게 2와 5인 물건을 고르면 가치 10입니다. 한 배열로 갱신할 때 용량을 감소 방향으로 순회해야 같은 물건을 중복 사용하지 않습니다. N <= 20에서는 모든 subset과 비교하고 W=0, 모든 물건이 너무 무거운 경우를 검사합니다.