구간 DP

구간 DP

저자 Андрей Гаркавый Сергей Слотин

상태가 어떤 배열의 접두사 또는 연속된 부분 구간인 DP 연습 문제 몇 가지를 살펴보겠습니다.

#메뚜기

$1 \times n$ 크기의 띠가 있습니다. 메뚜기는 첫 번째 칸에 서 있으며, 앞으로 1칸, 2칸 또는 3칸을 뛸 수 있습니다. 시작 칸에서 마지막 칸까지 가는 방법은 몇 가지입니까?

점화식을 세워 봅시다. 즉, $n$에 대한 답이 더 작은 수에 대한 답에 어떻게 의존하는지 유도해 봅시다.

$f[k]$를 1번 칸에서 $k$번 칸까지 가는 방법의 수라고 합시다. 처음 몇 개의 값을 직접 계산해 봅시다:

  • $f[1] = 1$가지 방법 (제자리에 서 있기)
  • $f[2] = 1$가지 방법:
$$ 1 \rightarrow 2 $$
  • $f[3] = 2$가지 방법이 있습니다:
$$ \begin{aligned} 1 \rightarrow 2 \rightarrow 3 \\ 1 \rightarrow 3 \end{aligned} $$
  • $f[4] = 4$가지 방법:
$$ \begin{aligned} 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \\ 1 \rightarrow 3 \rightarrow 4 \\ 1 \rightarrow 2 \rightarrow 4 \\ 1 \rightarrow 4 \end{aligned} $$
  • $f[5] = 7$가지 방법이 있습니다:
$$ \begin{aligned} 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \\ 1 \rightarrow 3 \rightarrow 4 \rightarrow 5 \\ 1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \\ 1 \rightarrow 4 \rightarrow 5 \\ 1 \rightarrow 2 \rightarrow 3 \rightarrow 5 \\ 1 \rightarrow 3 \rightarrow 5 \\ 1 \rightarrow 2 \rightarrow 5 \end{aligned} $$

이후부터는 더 어려워집니다. 하지만 규칙성을 발견할 수 있습니다. 물론 발견하지 못할 수도 있습니다. 어느 경우든, 공식을 생각해 내고 나면 처음 몇 개의 값을 적어 둔 상태에서 그 공식이 맞는지 아닌지 쉽게 확인할 수 있습니다.

메뚜기가 $n$번째 칸까지 가는 경로에서 마지막 점프는 어떤 것이었을 수 있는지 생각해 봅시다. 다음 세 가지 경우 중 하나입니다.

  • $(n - 1) \rightarrow n$
  • $(n - 2) \rightarrow n$
  • $(n - 3) \rightarrow n$

즉, $n$까지의 모든 경로는 3개의 그룹으로 나뉘며, 게다가 우리는 각 그룹에 경로가 몇 개 있는지도 알고 있습니다. 첫 번째 그룹에는 정확히 $f[n-1]$개의 경로가 있습니다. $(n-1)$번째 칸까지 가는 경로가 그만큼 있고, 그 뒤에 점프가 한 번 더 이어지기 때문입니다. 마찬가지로 두 번째 그룹과 세 번째 그룹에는 각각 $f[n-2]$개와 $f[n-3]$개의 경로가 있습니다.

세 그룹의 경로 수를 모두 합하면 다음을 얻습니다.

$$ f[n] = f[n-3] + f[n-2] + f[n-1] $$

피보나치 수와 매우 비슷하지 않습니까? 실제로 메뚜기가 앞으로 1칸 또는 2칸만 뛸 수 있다면, 답은 정확히 $n$번째 피보나치 수가 됩니다.

이 DP를 계산하기 위해 마찬가지로 배열을 하나 만들고 왼쪽에서 오른쪽으로 순회하며 채워 나갈 수 있습니다:

f[0] = 1
f[1] = 1
f[2] = 2
for (int i = 3; i < n; i++)
    f[i] = f[i - 3] + f[i - 2] + f[i - 1];

참고. 이러한 수열을 트리보나치 수라고 합니다.

연습 문제. 길이가 $n$인 0과 1로 이루어진 수열 중 1이 세 번 연속으로 나오지 않는 수열의 개수를 구하십시오.

#장애물이 있는 메뚜기

문제를 조금 바꾸어 봅시다. 이제 일부 칸은 막혀 있습니다. 즉, 특정한 몇몇 칸에는 메뚜기가 뛰어오를 수 없다는 것을 알고 있습니다.

그러면 이 문제는 여전히 같은 점화식으로 풀 수 있으며, 다만 모든 금지된 $k$에 대해 $f[k] = 0$임을 확인하기만 하면 됩니다.

구현에 이러한 검사를 추가해야 하므로, 각 크기의 점프를 따로따로 고려하지 않도록 코드를 약간 리팩터링하고, 또한 $f_1$만 초기화하겠습니다:

// a -- булевый массив, свободна ли i-ая клетка

f[0] = a[0];

for (int i = 1; i < n; i++)
    for (int j = i; j > max(i - 3, 0); j--)
        // f[i] изначально заполнены нулями
        f[i] += f[j] * a[j];

이러한 구현은 임의의 점프 길이 $k$에 대해서도 확장된다는 점에 주목하십시오. 시간 복잡도는 $O(n k)$입니다.

#부분 회문의 개수

$a_i = a_{n-i}$를 만족하는 길이 $n$의 문자 시퀀스 $a_i$를 팰린드롬이라고 합니다.

길이가 $n$인 주어진 문자열에 대해, 그 부분 문자열 중 몇 개가 팰린드롬인지 구해야 합니다.

부분 문자열 $l$부터 $r$까지가 팰린드롬이면 1, 그렇지 않으면 0인 DP $f[l, r]$를 정의합시다. 이를 계산하면 원래 문자열에서 팰린드롬인 부분 문자열을 모두 찾을 수 있으며, 답을 구하려면 이 DP의 모든 칸을 더하기만 하면 됩니다.

팰린드롬의 정의는 다음과 같이 달리 표현할 수도 있습니다. 문자열 $s$가 팰린드롬이라는 것은 $s_0 = s_n$이고 문자열 $s_{1\ldots n - 1}$이 팰린드롬이라는 뜻입니다. 바로 이 정의를 DP를 갱신하는 데 사용하겠습니다.

$$ f[l, r] = (s_l = s_r) \land f[l + 1, r - 1] $$

DP를 저장할 2차원 배열을 만들고 기저 사례를 살펴봅시다. 크기가 1인 부분 문자열은 항상 팰린드롬이고, 크기가 2인 부분 문자열은 첫 번째 문자가 두 번째 문자와 같으면 팰린드롬입니다. 나머지 상태에 대해서는 위의 공식을 사용하겠습니다.

유일하게 주의할 점은 순회 순서입니다. for 문으로 단순히 $l$이 증가하는 순서로 먼저 돌고 그다음 $r$이 증가하는 순서로 돌 수는 없습니다. 갱신이 더 큰 $l$의 DP 값에 의존하기 때문입니다. 대신 부분 문자열의 크기 $d = r - l + 1$을 기준으로 반복하고, 그다음 해당 크기의 모든 부분 문자열을 순회합시다. 그러면 어떤 부분 문자열에 대해서도 $f[l + 1][r - 1]$의 DP 값은 이미 계산되어 있습니다.

bool f[n][n];

for (int i = 0; i < n; i++) {
    f[i][i] = true;
    f[i][i + 1] = (s[i] == s[i + 1]);
}

for (int d = 3; d <= n; d++)
    for (int l = 0, r = l + d - 1; r < n; l++, r++)
        f[l][r] = (s[l] == s[r]) && f[l + 1][r - 1];

int ans = 0;
for (int l = 0; l < n; l++)
    for (int r = l; r < n; r++)
        ans += f[l][r];

또는 $l$이 감소하고 $r$이 증가하는 순서로 순회할 수도 있습니다. 또한 짝수 길이 팰린드롬의 기저 상태로 항상 팰린드롬인 ‘길이가 0인 부분 문자열’을 선택할 수도 있는데, 이는 반복문에서 f[i][i - 1] = true를 실행하면 됩니다. 아니면 아예 DP 배열 전체를 1로 초기화하고 $d=2$부터 시작해도 됩니다:

memset(f, 1, sizeof f);

for (int l = n - 1; l >= 0; l--)
    for (int r = l + 1; r < n; r++)
        f[l][r] = (s[l] == s[r]) && f[l + 1][r - 1];

이 문제에는 선형 시간 해법을 포함하여 더 최적화된 해법들이 있다는 점을 짚어 둡니다.