경우의 수 구하기

typedef long long ll;
ll cache[MAX_N][MAX_N];

//use dp
ll comb(int n,int r)
{
    if(r==0||n==r)return 1;
    ll&ret=cache[n][r];
    if(ret!=-1)return ret;
    return ret=comb(n-1,r-1)+comb(n-1,r);
}

//if n is small
ll comb(int n,int r)
{
    if(r==0||n==r)return 1;
    return comb(n-1,r-1)+comb(n-1,r);
}

 

nCr=(n-1)C(r-1)+(n-1)Cr

점화식을 이용한 간단한 재귀함수이다.

경우의 수의 특성상 수가 조금만 커져도 int범위를 간단히 넘어버리니 왠만한 경우에는 long long 을 선언해서

풀어주어야 한다.