코딩테스트
구간 dp 정리 (interval dp)
구간 dp 기본적인 dp 는 보통 아래와 같이 시작~ 끝지점까지를 구하는 것으로 '전체의 최대 or 최소'를 찾는다. dp[n] => 0~n까지의 최대or 최소 하지만, 이런식으로는 해결하지 못하는 문제도 존재한다. 만약 시작점-끝점이 아닌, '구간'에 대해 최소 or 최대 등을 bottom-up 방식으로 dp로 풀어나가기 위해선 이중배열을 기반으로 구간 dp를 구성해야한다. 구간 dp의 반복문은 보통 아래와 같다. for( 구간의 길이) for(시작점~ 시작점-길이 )// 시작점 선택 -> ( 끝점 = 시작+길이이기에 자동으로 시작~ 끝 구간 선택 가능) bottom-up 을 수행해야하기에, '구간의 길이' 가 커지는 순서로 구성해야한다. 그래야 1~3 구간을 [1~1], [2~2], [3~3], [1..
