DP 점화식 패턴

내가 지금까지 DP 문제를 풀면서 어느정도 패턴이 있다고 생각하여, 그 패턴을 정리 해보려고 한다.

하지만 무조건 여기에 정리한 패턴이 나오는건 아니다. 그래도 한 번 정리하고 넘어가면 다음에 비슷한 문제는 해결할 수 있을것 같다.

 

- 현재까지 계산된 값을 넣어놓는 패턴

1. n개의 배열 (arr[n])이 주어지면 arr[0]부터 arr[i]까지의 무언가 연산한 결과를 D[i]에 넣는다.

2. 이때 기준이 있어야 하므로 2중 for문을 사용한다.

3. D[i]는 D[j]와 arr[i]를 연산하는 것 생각해본다. 

4. 내가 가장 많이 하는 실수는 요소의 기준을 항상 요소의 처음부터라고 생각한다.

   요소의 끝을 먼저 정하고 풀이를 생각해보자.

 

- 선택지를 주고 이 중에서 하나를 선택하는 패턴

1. D[i]는 문제에서 주어진 선택지 중 하나를 선택했을 때 들어갈 수 있는 수를 넣는다.

2. 예를들어 주어진 현재 배열을 선택하지 않거나 선택할 수 없을 경우, D[i-1]와 현재를 선택때와 비교하면 된다.

3. i 는 현재를 의미하지만, 세부적으로 봤을 땐 문제에서 주어진 선택지를 모두 둘러보고 그 중 문제에서 원하는 결과와 가장 근접한 값을 선택한것이다.

 

 -선택을 하면 제한이 걸리는 패턴

바로 위에 선택지를 주는 패턴과 비슷해보이지만 해당 패턴은 A를 선택하면 무조건 C를 선택할 수 밖에 없는 그런 경우이다. (느낌이 그렇다는것)

 

1. D[i][j] 와 같이 이중배열로 선언 한다. i는 현재, j는 문제에서 주어진 경우이다.

2. j를 정하면 나머지 경우는 일어나지 않는것으로 계산해야한다. (j = A 이면 A를 선택했을 때 일어날 수 있는 경우의 수만 생각한다.) 

 

<문제를 풀다가 많이 마주치는 문제가 있으면 정리 할 것>