차원 선택 기준
DP 차원 선택 기준
직전 값만 필요한지, 두 축의 관계가 필요한지, 방문 집합이 필요한지를 먼저 가릅니다.
1차원
이전 인덱스나 직전 상태만으로 다음 값을 만들 수 있을 때 씁니다.
2차원
두 문자열, 행렬 좌표, 무게와 가치처럼 축 두 개가 얽힐 때 씁니다.
그래프
정점 순서나 DAG 위상 순서가 전이 방향을 결정할 때 씁니다.
비트마스크
방문 집합 자체가 상태 의미에 포함될 때만 사용합니다.
차원 선택 기준
직전 값만 필요한지, 두 축의 관계가 필요한지, 방문 집합이 필요한지를 먼저 가릅니다.
이전 인덱스나 직전 상태만으로 다음 값을 만들 수 있을 때 씁니다.
두 문자열, 행렬 좌표, 무게와 가치처럼 축 두 개가 얽힐 때 씁니다.
정점 순서나 DAG 위상 순서가 전이 방향을 결정할 때 씁니다.
방문 집합 자체가 상태 의미에 포함될 때만 사용합니다.