동적계획법 PS 팁

동적계획법이란 큰 문제를 같은 해법을 가지는 재귀적인 부분문제들로 나눠서 각각의 해를 더해나가며 

 

큰 덩어리의 해를 구하는 알고리즘이다.

 

문제 난이도가 올라갈 수록 점화식이나 DP테이블을 만들 때 어떻게 만들어야 할지 헷갈린다.

 

그래서 테이블 형태를 구상하거나 점화식을 구현할 때 도움이 됐던 팁 몇가지를 적어보겠다.

 

1. 문제 단계 분할

• 말 그대로 문제를 단계별로 분할한다. 이전 단계와 현재 단계에 관계가 있도록 분할 해야한다.
• 다음 단계의 최적해를 유추해 낼 때 현재(혹은 이전) 단계의 최적해를 사용해야한다. 
• 만약 다음 단계의 최적해를 유추해 낼 때 현재 단계의 최적해를 전혀 사용하지 않는다면 
  문제를 잘못 이해했을 가능성이 상당히 높다.

2. 각 단계마다 영향을 주는 요소 갯수로 테이블 생성

• - 만약 각각의 단계에 영향을 주는 요소가 1개일 경우 1차 배열, 2개일 경우 2차 배열인 식이다.
• - dp[요소1][요소2]... 에 최적값을 계산하고 메모이제이션

 

3. 중복 계산되는 부분 찾기

• 대부분의 DP 문제들은 변별력을 위해서 문제를 브루트포싱 방법을 푼다면 시간 초과 / 메모리 초과를 내도록 한다. |즉, 완전탐색 풀이를 했을 때 중복계산이 많이 나도록 하여 풀이 시간을 늘리는 것이다.
• 이를 이용해 중복계산이 나는 부분을 찾아서 점화식을 역으로 유추 할 수도 있다.