메모이제이션을 활용한, 이항계수 구하기 in C++

n개의 원소에서, r개를 뽑아 부분집합을 만드는 경우의 수를 구하는 코드(nCr)

#include <iostream>

using namespace std;
int dp[51][51];
int n, r;

int DFS(int n, int r) {
    if (dp[n][r] > 0) return dp[n][r];
    else if (n == r || r == 0) return 1;
    else return dp[n][r] = DFS(n - 1, r) + DFS(n - 1, r - 1);

}

int main() {
    freopen("input.txt", "rt", stdin);
    cin >> n >> r;
    cout << DFS(n, r);
    return 0;
}

• else if (n == r || r == 0) return 1 : 종료 조건
  
• return dp[n][r] = DFS(n - 1, r) + DFS(n - 1, r - 1) : 메모이제이션을 활용
  
  

ex)
5 3