如何用偏基础的c语言递归和动态规划解决该问题

Question

如何用偏基础的C语言递归程序和动态规划程序分别解决这个问题，希望给出两种方法
数据范围在一千左右

Answer 1

代码如下：
（1）递归

#include <stdio.h>

long long Cnk(int n,int k)
{
    if(k==0 ||k==n)
        return 1;
    else
        return Cnk(n-1,k)+Cnk(n-1,k-1);
}


int main()
{
    int n,k;
    long long res = 0;
    scanf("%d %d",&n,&k);
    res = Cnk(n,k);
    printf("%lld",res);
    return 0;
}

（2）

#include <stdio.h>
long long Jiecheng(int n)
{
    long long s = 1;
    for(int i=1;i<=n;i++)
        s *= i;
    return s;
}


long long Cnk(int n,int k)
{
    return Jiecheng(n)/Jiecheng(k)/Jiecheng(n-k);
}


int main()
{
    int n,k;
    long long res = 0;
    scanf("%d %d",&n,&k);
    res = Cnk(n,k);
    printf("%lld",res);
    return 0;
}