개인적인 DP 문제 풀이법 정리

1. 경우의 수일 경우 1부터 차근히 경우의 수를 구하고 수식을 찾는다. 경우의 수가 변하는 분기를 기준으로 리스트에 값을 넣고 점화식을 이용하여 문제를 푼다.

 

2. 최적의 값 혹은 해를  찾는 경우, 각 인덱스 값에 현재 가장 최적인 값을 찾는 식을 찾아야 한다. 일단 모든 리스트를 최소의 최적 값으로 초기화한다. 이후 작은 값부터 최적의 값을 채우는 경우를 찾아야 한다.

 

보통 단계로 쪼개져 비교하는 경우와 배열 중 가장 긴 무언가를 찾는 경우, 혹은 리스트를 가장 큰 값 혹은 작은 값으로 유도하는 경우가 있다.

 

이를 위해서 쪼개는 경우는 쪼개진 경우에서 각각 최적의 값을 채우고 반복되서 비교되는 식을 세우면 어느 정도 해결이 된다. 

 (계단 오르기)

 

가장 긴 무언가를 찾는 경우는 각 인덱스의 값과 인덱스 기준의 전 값들을 비교하여 만족하는 최대의 길이를 DP 배열의 인덱스 값에 넣어주면 된다.

(가장 긴 감소하는 부분 순열)

 

특정 값의 유도는 전 값에 의해 채워진 DP의 특정 인덱스를 현재 들어가는 값과 어떻게 비교하여 DP에 넣어줄 것인 지를 파악해야한다. 

(퇴사 2)