DP 차원 정의
1차원과 2차원 DP 선택은 취향이 아니라, 상태가 기억해야 할 축이 몇 개인지에 따라 결정됩니다.
한 축으로 충분
LIS, 동전 조합처럼 하나의 인덱스 또는 합으로 상태를 표현합니다.
두 축 정보 필요
LCS처럼 문자열 A 위치와 B 위치를 동시에 기억합니다.
차원은 비용
상태 수가 시간과 메모리의 상한을 결정합니다.
압축은 나중에
정답형 2차원 구현을 검증한 뒤 1차원 압축을 적용합니다.
1차원과 2차원 DP 선택은 취향이 아니라, 상태가 기억해야 할 축이 몇 개인지에 따라 결정됩니다.
LIS, 동전 조합처럼 하나의 인덱스 또는 합으로 상태를 표현합니다.
LCS처럼 문자열 A 위치와 B 위치를 동시에 기억합니다.
상태 수가 시간과 메모리의 상한을 결정합니다.
정답형 2차원 구현을 검증한 뒤 1차원 압축을 적용합니다.