Dynamic programming, 동적 계획법

피보나치 수열 구하기(그냥 일반항에 대입하면 나오기는 하지만) 처럼 최종 결과를 도출하기 위해서 이를 더 작은 단위의 문제로 나눠서 먼저 해결하고 그것을 조합하여 최종 문제를 해결하는 방법을 말한다.

* 분할 정복과 비슷하나, 분할 정복은 분할된 문제가 서로 영향을 주지 않아 독립적으로 해결 가능하다는 차이점이 있다.

Top-down(Memoization)과 Bottom-up으로 나뉜다.

2017/06/02 - [Web/Front-end] - [JS] memoization, currying

Buttom-up 방식의 fibonacci 수열 구하기

```python

def fib(n):

    arr = [0] * n

    arr[1] = 1

    arr[2] = 1

    for i in range(3, n):

        arr[i] = arr[i-1] + arr[i-2]

    return arr[n-1]

```

Top-down은 최종 값에서 시작해서 재귀를 통해 끝까지 내려갔다가 resolve하면서 올라오는 방식.

Bottom-up은 앞에서 부터 차례차례 구해나가면서 최종 값에 다다르는 방식.

DP로 풀 때 고려할 점.

일단 메모이제이션쪽으로 사고해서 최종 결과에서 부터 결과 직전의 값으로 타고내려가는 Top-down식을 세운 다음, 이를 Bottom-up 방식으로 고치는 것을 생각해본다.

단, 이 때 약간 직관에서 벗어난, 더 느릴 것 같다는 느낌의 사고를 해야 Bottom-up으로 고칠 수 있는 경우도 종종 있다. 예를 들어 주어진 데이터에 linear하게 접근한다던가...