다이나믹 프로그래밍

작은문제를 풀어서 큰 문제를 푸는데 도움이 되자!

1. 문제가 원하는 정답을 찾기 위해 가장 먼저 완전탐색 접근 시도
2. 탐색하는 경우가 지나치게 많아서 안될 것 같을때
3. 이럴때 빠르게 탐색 하는 다이나믹 프로그래밍 시도

규격화 된 다이나믹 프로그래밍 법

1. 풀고 싶은 가짜 문제 정의
   1. Dy[i] : 1~ i 번 원소에 대해서 조건을 만족하는 경우의 수
2. 가짜문제를 풀면 진짜 문제를 풀 수 있는가 ?
   1. 진짜문제 : A[1….N] 조건을 만족하는 부분 수열의 개수
   2. 가짜문제 : Dy[i] : 수열 A[1…i] 에서 조건을 만족하는 부분 수열의 개수
3. 초기값은 어떻게 되는가 ?
   1. 가장 작은 문제 해결하기
4. 점화식 구해내기
   1. 점점 더 큰 문제들을 해결하면서 Dy배열을 가득 계산하는 과정
5. 진짜 문제 정답 출력
   1. 성공적이지 않다면 1~로 돌아가서 다시 반복

규격화된 형태가 있고 그렇기 때문에 코딩양은 적다

없는 것을 만들어야함

문제속의 숨은 것을 찾아야 한다는 점이 어렵다!

가짜문제 잘못된 정의 시 — 필요한 정보를 문제에 추가하기

진짜문제 : N번째 계단에서 도착하며 얻는 최대 점수

가짜문제 →
Dy[i][0] : = i-1 번째 계단은 밟지 않고, i 번째 계단에 도착하며 얻는 최대 점수

Dy[i][1] : = i-1 번째 계단을 밟고서, i 번째 계단에 도착하며 얻는 최대 점수

Dy[i][0] = max(Dy[i-2][1] + A[i] , Dy[i-2][0] + A[i])

Dy[i][1] = Dy[i-1][0] + A[i]

동적 프로그래밍을 진짜 할 수 있다면

역 추적 Backtrack 이 필요함

실제로 어떻게 밟아야 하냐 ?

어떤 칸들을 밟아야 하냐

테이블을 가득 채우고 마지막 값을 보며 뒤로 돌아감

어떤 파티션에서 왔는가? 를 기록해주자

Come[i][0] {(i-2,1),(i-2,0)} 둘 중 하나를 기록

Table을 채워 나갈 때 기록을 함께 한다면 실제 방법도 찾을 수 있다.

이를 역추적 BackTrack이라고 한다.

---

풀고 싶은 가짜 문제 정의

1. 문제크기 N을 변수로 만들어 표기하는 경우
   1. Dy[i] = i 를 1,2,3의 합으로 표현하는 경우의 수
   2. Dy[i] = 2*i 타일링 경우의 수
2. 문제크기 N과 마지막 상태를 함께 기록해야 하는 경우
   1. 계단오르기
      1. Dy[i][0] := i-1번째 계단은 밟지 않고, i번째 계단에 도착하며 얻는 최대 점수
      2. Dy[i][1] := i-1번째 계단을 밟고서, i번째 계단에 도착하며 얻는 최대 점수
   2. 오르막 수
      1. Dy[i][last] = 길이가 i 이며 last로 끝나는 오르막 수의 개수
3. 구간 L~R에 대한 문제를 해결할 때
4. 2차원 격자 배열에서 문제를 해결할 때
5. 트리 구조에서 문제를 해결할 때