Top-down

상관관계 없는 문제 분할 정복한다

• 팩토리얼
• 퀵정렬,병합정렬
• DFS

피보나치 , 행렬곱셈최적 순서 문제에는 하면 안됨.

점화식으로 구한다.

nC0=nCn=1
r>0이면,nCr=n-1Cr-1+n-1Cr

중복 계산 생길 수 있다.

이건 메모리로 해결 하면 된다.

특히 피보나치는 미친 시간을 걸리게 한다.

메모이제이션을 쓰자!!

long fibo(int n){
    long memo[max];
    if(memo[n]>0){
        return memo[n]
    }

    if(n==1 || n==2) {
        retrun memo[n]=1;
    }else{
        return memo[n] = fifo(n-1) + fibo(n-2);
    }
}

금액 맞추기

지폐 종류 : 1만원,2만원,5만원,20만원,50만원

지불 금액 : 100만원

1) 50만원을 안 내고 1,2,5,20만원으로 100만원을 만드는 경우의 수

2) 50만원 한 장을 내고 1,2,5,20만원으로 50만원을 만드는 경우의수

3) 50만원 두 장을 내고 1,2,5,20만원으로 0만원을 만드는 경우의 수

이처럼 작은 문제로 나눌 수 있다.

문제를 정의하고

식을 정의

수분할

그레이코드