풍선 터뜨리기: 역방향 구간 DP

nums 값을 가진 n개의 풍선이 주어질 때, 풍선 i를 터뜨리면 nums[i-1] * nums[i] * nums[i+1]만큼의 코인을 얻습니다(자기 자신과 현재 이웃 풍선 값의 곱입니다). 풍선이 터진 뒤에는 이웃 풍선들이 서로 인접하게 됩니다. 모든 풍선을 터뜨려 얻을 수 있는 최대 코인을 구하십시오. 단순한 시뮬레이션은 풍선을 터뜨릴 때마다 이웃이 바뀌므로 어렵습니다. 역방향 구간 DP는 이 어려움을 우아하게 피해 갑니다.

dp[i][j]를 구간 [i, j]의 풍선을 터뜨려 얻는 최대 코인으로 정의하고 어떤 풍선을 먼저 터뜨릴지 생각해 보겠습니다. 풍선 k를 먼저 터뜨리려면 nums[k-1]과 nums[k+1]이 현재 이웃이어야 합니다. 하지만 이 풍선들은 나중에 터질 수 있으므로 이웃이 동적으로 바뀝니다. 정방향으로는 상태를 깔끔하게 정의하기 어렵습니다.

핵심 요령은 구간 [i, j]에서 어떤 풍선이 마지막에 터지는지를 생각하는 것입니다. 풍선 k가 [i, j]에서 마지막으로 터질 때는 [i, j]의 다른 모든 풍선이 이미 사라진 상태입니다. 따라서 풍선 k의 이웃은 정확히 nums[i-1]과 nums[j+1]이며, 이는 구간 바로 바깥의 경계 풍선입니다. 그러므로 마지막에 터뜨릴 때 얻는 코인 계산은 결정적이며, 앞선 풍선을 터뜨린 순서에 영향을 받지 않습니다.

경계용 풍선을 추가합니다. nums의 앞과 뒤에 1을 추가하여 nums = [1] + nums + [1]로 만듭니다. dp[i][j]를 인덱스 i와 j 사이에 엄밀히 포함되는 모든 풍선을 터뜨려 얻는 최대 코인으로 정의합니다. 이때 nums[i]와 nums[j]는 살아남는 경계 풍선입니다. 점화식은 다음과 같습니다. (i, j) 안의 마지막 풍선 후보 k 각각에 대해 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])를 계산합니다.

배열에 경계용 풍선을 추가하고, DP 표를 0으로 초기화합니다(빈 구간 = 코인 0개). 그런 다음 구간 길이가 증가하는 순서로 채웁니다. 최종 답은 dp[0][n+1]이며, 이는 경계용 풍선을 영구적인 경계로 두고 원래의 모든 풍선을 터뜨려 얻는 최대 코인을 나타냅니다.

[3, 1, 5, 8]을 [1, 3, 1, 5, 8, 1]로 확장하면 인덱스는 0-5가 됩니다. 우리가 구할 값은 dp[0][5]입니다. 길이가 2인 구간(내부 풍선 하나)에 대해서는 dp[0][2] = 1*3*1=3, dp[1][3]=3*1*5=15, dp[2][4]=1*5*8=40, dp[3][5]=5*8*1=40입니다. 계산을 확장해 나가면 이웃 풍선들을 먼저 터뜨린 뒤 {3,1,5,8} 중 1을 마지막에 터뜨리는 것이 최적이며, 총 코인은 167개입니다.

O(n²)개의 구간이 있고 각 구간에서 O(n)개의 분할 지점을 시도하므로 O(n³) 시간 복잡도가 됩니다. 공간 복잡도는 DP 표에 필요한 O(n²)입니다. n = 500개의 풍선이라면 1억 2,500만 번의 연산이며, 면접의 제한 조건에서는 충분히 가능합니다. 경계용 값을 추가하면 경계 처리가 단순해집니다. 이를 사용하지 않으면 i-1과 j+1이 범위 안에 있는지 직접 확인해야 합니다.

같은 해법을 @lru_cache를 사용하는 하향식 방식으로 작성할 수도 있으며, 면접에서 도출하기에는 이 방식이 더 직관적일 수 있습니다. solve(i, j)를 열린 구간 (i, j)에서 얻는 최대 코인으로 정의합니다. 이 함수는 모든 k를 마지막에 터뜨릴 풍선으로 시도하고 결과를 메모이제이션합니다. 두 접근법의 시간 및 공간 복잡도는 같습니다.

흔한 실수는 dp[i][j]를 구간 [i,j]에서 첫 번째로 터뜨릴 풍선에 대한 코인으로 정의하는 것입니다. 이렇게 하면 첫 번째 풍선을 터뜨릴 때의 코인 계산이 아직 터뜨리지 않은 이웃 풍선에 의존하므로 실패합니다. 알고리즘이 진행되면서 이웃 풍선의 상태도 바뀌기 때문입니다. 경계가 남아 있는 원소에 의존하는 구간 DP에서는 항상 구간의 마지막 원소를 생각하십시오.

값이 1인 경계용 풍선을 선택하는 이유는 곱셈의 항등원으로 작용하기 때문입니다. 경계 풍선이 마지막에 터질 때 그 코인 값은 boundary * last * boundary = 1 * last * 1 = last가 됩니다. 0을 사용하면 코인이 0이 되어 잘못되고, 다른 값을 사용하면 계산이 왜곡됩니다. 경계용 풍선 기법을 사용하면 가장 왼쪽과 가장 오른쪽 풍선을 별도로 처리하지 않고 모든 경계 사례를 깔끔하게 통합할 수 있습니다.

표준 구간 DP(행렬 연쇄 곱셈)에서는 분할 지점 k가 문제를 서로 독립적으로 해결할 두 하위 문제로 나누는 위치를 나타냅니다. 풍선 터뜨리기에서는 k가 구간에서 마지막에 터지는 풍선을 나타냅니다. 따라서 k가 여전히 경계로 남아 있다는 조건에서 두 하위 구간 [i,k]와 [k,j]는 독립적입니다. 이러한 역방향 관점이 풍선 터뜨리기를 구간 DP로 해결하게 해 주는 핵심 발상입니다.

이 수업에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해를 확인하십시오.

이 수업에서 배운 내용은 다음과 같습니다. 풍선을 정방향으로 터뜨리는 시뮬레이션은 이웃이 예측할 수 없이 바뀌기 때문에 실패합니다, 역방향 관찰을 통해 구간에서 마지막으로 터지는 풍선을 k로 정의하면 이웃은 nums[i]와 nums[j]가 됩니다, 그리고 센티널을 덧붙인 점화식 dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])은 O(n³) 해법을 제공합니다. 다음에는 고전적인 0/1 배낭과 그 공간 최적화부터 시작해 배낭 DP로 넘어갑니다.