[C++] 이항계수(메모이제이션)

#include <iostream>

int dy[21][21]; //1. 0으로 초기화 돼있었는데
int DFS(int n, int r){
    if(dy[n][r] > 0) return dy[n][r];//3. 곧바로 리턴한다(이미 구했다고 생각하고)
    if(n==r || r == 0) return 1;
    else return dy[n][r] = DFS(n-1,r-1)+DFS(n-1,r); //2. 값이 들어갔다면
    //nCr = n-1Cr-1 + n-1Cr
}

int main() {
    int n,r;
    scanf("%d %d",&n,&r);
    printf("%d\n",DFS(n,r));
    return 0;
}

• 이항계수는 nCr = n-1Cr-1 + n-1Cr 이라는 공식이 성립된다.
• 그리고 nCr ( n== r)이거나 nC0인 경우 그 값은 1이다.
• 따라서 값이 1이 될때까지 재귀적으로 트리를 만들어 나가면 된다.
• 이 때, 중복적으로 구하는 이항계수 값이 많아져 불필요한 자식노드가 만들어지는 것을 방지하기 위해
• 메모이제이션을 통해 배열에 저장해놓고
• 해당 배열에 이미 값이 있다면 그 값을 리턴하는 방식으로 진행한다.

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard