memorization / 조합 combination

 순환을 이용한 조합

m 배열에 값을 메모한다.

#include<stdio.h>
int comb(int n, int r, int *m);
int main()
{
    int c;
    int i;
    int n, r;
    int *m;
    printf("enter number n and r (nCr)\n");
    printf("n:");
    scanf("%d", &n);
    printf("r:");
    scanf("%d", &r);
 
    m = (int*)malloc(sizeof(int) * (r + 1));
    for (i = 0; i <= r; i++)
        m[i] = 0;
    c = comb(n, r, m);
    printf("%d", c);
 
    return 0;
}
int comb(int n, int r, int *m)
{
    if (r == n || r == 0)
        return 1;
    if (n - 1 == r)
    {
 
        if(m[r] == 0)
            m[r] = comb(n - 1, r - 1, m) + comb(n - 1, r, m);
        return m[r];
    }
   
    return comb(n - 1, r - 1, m) + comb(n - 1, r, m);
}