# Dynamic Programming[1] - 이항계수

# Fibonacci Numbers : 1 1 2 3 5 8 13 ...

f(n) = f(n-1) + f(n)

=> f(x)를 구하기 위해서 그 전들의 값을 알아야 한다. 그런데 여기서 여러가지의 x값을 사용하여 여러가지의 f(x)값을 구한다고 가정할때 중복되는 계산 단계가 다수 발생한다.

* 중복 계산을 피하기 위한 방법

1) f(x)을 계산을 할때마다 저장되지 않은 중간 계산 결과를 caching(저장)한다.

2) bottom-up 방식으로 f(0)부터 구하고자하는 f(x)까지 모두 구한다, 이렇게 되면 다른 f(x)도 쉽게 계산할 수 있다.

 

# 이항 계수 (Binomial Coefficient)

- 이항/다항 정리

 

=> 역시 많은 계산이 중복이 된다.

=> 이 역시도 bottom-up방식으로 2차원 table에 저장을 하여 풀수있다.

#include<stdio.h>
int binom[100][100] = { 0 };
 
int binomial(int n, int k)
{
    int i = 0, j = 0;
    for (i = 0; i < n; i++) 
    {
        for (j = 0; j <= k && j <= i; j++) 
        {
            if (j == 0 || n == k) {
                binom[i][j] = 1;
                printf("binom[%d][%d]=%d \n", i, j, 1);
            }
            else {
                binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
            }
        }
    }
    return binom[n][k];
}
 
void main()
{
    int result = binomial(5, 3); // 5개중에 3개를 뽑을수 있는 횟수
    printf("%d",result);
}

# Memoization VS Dynamic Programming

- 순환식의 값을 계산하는 기법들이다.

- 둘 다 동적계획법의 일종으로 보기도 한다.

- Memoization은 top-down방식이며, 실제로 필요한 subproblem만을 푼다, recursion에 수반되는 overhead를 감수해야한다.

- 동적계획법은 bottom-up방식이며, recursion에 수반되는 overhead가 없다.