Combination

옛날에 했던거.. 5C2이런거

이것도 말이 됨.

3을 포함하지 않는 경우의 수 4C2 + 4 == 5C2

지금 PPT오타있다.

Dynamic Programming

문제를 쪼개서 해결을 하는데 그 과정에서 반복되는 작업을 cache를 이용해서 불필요한 연산 안하게하는거.

자기 만의 스타일을 계속 지키는게 좋다.

1) 기저 사례 (예외)

2) 이미 답을 구한 적 있으면 바로 반환

3) 새로 답을 구해서 캐시에 저장

int cache[50][50];

int Combination(int n, int r)
{
    // 기저 사례
    if (r == 0 || n == r) return 1;

    // 이미 답을 구한 적이 있으면 바로 반환
    int& ret = cache[n][r];
    if (ret != -1) return ret;

    return Combination(n - 1, r - 1) + Combination(n - 1, r);
}

이런 거 엄청 자주 나온다