선형 DP는 dp[i]가 이전 몇 개의 값에만 의존하는 가장 기본적인 형태다. 1차원 배열 하나로 풀 수 있어서 DP 입문 문제의 대부분이 여기에 해당한다.
기본 형태
계단을 오르는 문제를 보자. N개의 계단이 있고, 한 번에 1칸 또는 2칸을 오를 수 있다. N번 계단에 도달하는 방법의 수는?
상태 정의 : dp[i] = i번 계단에 도달하는 방법의 수
점화식 : i번 계단에 오는 마지막 결정은 1칸 오르거나 2칸 오르거나.
dp[i] = dp[i-1] + dp[i-2]dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}dp[1] = 1 : 1번 계단에 오는 방법은 "1칸 오르기" 하나. dp[2] = 2 : 2번 계단에 오는 방법은 "1칸+1칸", "2칸" 두 가지.
조건이 추가되는 경우
"3칸 연속으로 오르면 안 된다"는 조건이 붙으면 상태 정의를 바꿔야 한다.
dp[i]에는 i번 계단에 도달하는 방법의 수가 들어가는데, "직전에 연속으로 몇 칸 올랐는지"에 따라 다음 선택이 달라진다. 이 정보가 상태에 포함되어야 한다.
dp[i][k] = i번 계단에 도달했을 때, 연속으로 정확히 k칸을 오른 경우의 수.
// k=1: 마지막에 1칸을 올라서 i에 도착
dp[i][1] = dp[i-1][1] + dp[i-1][2];
// k=2: 마지막에 2칸을 연속 올라서 i에 도착 (직전에 1칸 연속이었어야 함)
dp[i][2] = dp[i-2][1];이처럼 조건이 생기면 상태 변수를 추가해서 그 조건을 상태에 반영한다.
DP에서 상태는 "지금 어디에 있는가" 뿐 아니라 "어떻게 여기에 도달했는가"의 맥락도 담을 수 있다. 맥락이 다음 선택에 영향을 주면 반드시 상태에 포함해야 한다.
선형 DP의 전형적인 문제 유형
- 계단 오르기 / 타일 채우기 : 경우의 수,
dp[i] = dp[i-1] + dp[i-2]계열 - 최대 연속 합 (Kadane's Algorithm) :
dp[i]= i에서 끝나는 최대 부분합 - 최소 비용 경로 : 1D에서 특정 위치까지의 최소 비용
최대 연속 합의 점화식을 보면 선형 DP의 핵심이 잘 드러난다.
dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);dp[i-1] + arr[i] : 이전 구간을 연장 arr[i] : 현재부터 새로 시작
"연장하는 게 나은가, 새로 시작하는 게 나은가"를 매 위치에서 결정한다.