dimension first

DP 차원은 “기억해야 할 축”의 개수로 정한다

상태 차원은 취향이 아니라 필요한 정보량이다. 하나의 위치만 알면 1차원, 두 입력의 접두사를 같이 봐야 하면 2차원이 된다.

1D: 한 축 2D: 두 축 압축: 이전 행

상태 설계 순서

1
상태 의미

dp[i] 또는 dp[i][j]가 정확히 무엇을 뜻하는지 문장으로 쓴다.

2
필요한 축

현재 선택에 필요한 이전 정보가 하나인지 둘인지 센다.

3
전이 방향

이전 칸, 위 칸, 왼쪽 칸, 대각선 칸 중 무엇을 참조하는지 표시한다.

4
압축 가능성

이전 행만 필요하면 2D를 1D로 줄일 수 있는지 검토한다.

문제 구조 상태 예시 대표 문제
한 배열을 왼쪽에서 오른쪽으로 본다 dp[i] LIS, 계단, 동전 조합
두 입력의 접두사를 동시에 비교한다 dp[i][j] LCS, 편집 거리
직전 행만 참조한다 prev[j], cur[j] 공간 압축 가능