# 2-3

1. 일반적으로 **최적화 문제** 혹은 **카운팅 문제** 에 적용됨.
2. 주어진 문제에 대해 순환식을 정의
3. 순환식을 memoization or bottom-up으로 풀이.
4. 최적화 문제
   * 최소값, 최대값 구하는거
   * 근데 최단경로가 최소값은 아님. 경로의 최소 길이를 구하는 거라 똑같은 문제가 아닐 수 있음.

## 핵심 : 순환식

동적계획법의 핵심은 순환식.

* subproblem들을 풀어서 원래 문제를 푸는 방식. 그런 의미에서 분할정복법과 공통성이 있음.

> 순환식이란? 예를 들어, `L[i][j] = min( L[i-1][j], L[i][j-1] ) + path[i][j];` original problem을 subproblem들을 풀어서 해결

* 분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법은 그렇지 않음.
* 즉 서로 overlapping 하는 subproblem들을 해결하여 원래 문제를 해결.
  * `f(n) = f(n-1) + f(n-2)`
  * n-1에 관한 문제와 n-2에 관한 문제 즉, 2개의 subproblem의 문제를 해결 및 조합하여 original problem에 대한 해답을 구함.

### Optimal substructure인지 확인하는 질문

Optimal Substructure의 중요한 건 **순환식을 어케 세우는 것** 이냐이다. 그거슨 **최적해의 일부분이 그 부분에 대한 최적해인가?** 이다.

최단경로 문제로 예를 들어보자.

![img](https://2920326462-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVaojOGRpgbnZA-5MxU%2F-LXU8wI1R11SofR0LUyz%2F-LXU91-_6-EhnkJyKXYR%2F2-3-1.png?generation=1548858435112537\&alt=media)

**순환식은 optimal substructure를 표현**

![img](https://2920326462-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVaojOGRpgbnZA-5MxU%2F-LXU8wI1R11SofR0LUyz%2F-LXU91-bsiOMEIZDaGVb%2F2-3-2.png?generation=1548858435088039\&alt=media)

d\[v]라고 쓸 수 있는 이유는 d\[v]가 최적해이기 때문. 즉, d\[u]에 대한 최적해는 d\[v] + w(u,v)인데, d\[v]는 d\[u] 부분에 대한 최적해여야함.

#### 최장 경로 문제

* 노드를 **중복 방문하지 않고** 가는 가장 긴 경로
* optimal substructure를 가지는가?
* 순환식을 세우기 위한 젤 처음 해야 하는 질문
  * **이 문제에 대한 최적해의 일부분이 그 부분에 대한 최적해인가?**
  * 근데 이 특성이 당연히 성립되지 않음 (아래 그림 보자)

![img](https://2920326462-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LVaojOGRpgbnZA-5MxU%2F-LXU8wI1R11SofR0LUyz%2F-LXU91-dZ8Tr0i856ocb%2F2-3-3.png?generation=1548858435460265\&alt=media)

* 그럼 최장경로 문제는 optimal substructure를 갖지 않는 걸까?
* 그런건 아님.

## Summary

* 최적화, 카운팅과 같은 문제에 적용됨.
* 주어진 문제에 대해 순환식을 정의(가장 중요)
* 순환식을 memoization or bottom-up으로 풀이

**핵심은 순환식.**

* subproblem들을 풀어서 original 문제(더 큰 문제)를 푸는 방식.
  * 최단경로 문제를 생각해보자. `L[i][j] = min(L[i-1][j], L[i][j-1]) + path[i][j]`
  * 피보나치를 생각해보자. `f(n) = f(n-1) + f(n-2)`

그렇다면 어케 DP인지 즉, Optimal substructure인지 알 수 있을까? **구하고자 하는 최적해의 일부분이 그 부분에 대한 최적해인가** 로 설계가능 할 수 있어야함.