求组合c(n,m)的简单算法 （新手篇04）

问题分析：求c(n,m)
算法设计： c(n,m)=c(n-1,m-1)+c(n-1,m)使用备忘录法避免重复求解 题目要求动态规划求组合，刚好其规律符合杨辉三角，第n+1行第m+1列，那么只要用杨辉三角的算法算出那个数。空间占用较大 由于杨辉三角性质可转化为求杨辉三角第n行m列的值使用循环队列和递推动态规划计算
算法实现（备忘录法）：
def cjs(n,m,c):
if(nm):
c[n][m]=1
return
if(m1 or n-m==1):
c[n][m]=n
return
if(c[n-1][m-1]==0):
cjs(n-1,m-1,c)
if(c[n-1][m]==0):
cjs(n-1,m,c)
c[n][m]=c[n-1][m-1]+c[n-1][m]

源代码：
#include<stdio.h>
#include<stdlib.h>
void cjs(int n, int m, int** c)
{
if (n<m)
{
printf(“输入错误，请重新输入”); //防止输入错误
}
if (n == m)
{
c[n][m] = 1;
c[n][0] = 1;
return;
}
if (m == 1 || n- m == 1)
{
c[n][m] = n;
c[n][n - m] = n;
return;
}
if (c[n - 1][m - 1] == 0) //递归
cjs(n - 1, m - 1, c);
if (c[n - 1][m] == 0)
cjs(n - 1, m, c); //递归
c[n][m] = c[n - 1][m - 1] + c[n - 1][m]; //求解
}
int main()
{
while(1)
{ int n, m;
printf(“请输入n和m的值\n”);
scanf("%d %d", &n, &m);
int** c = (int**)calloc(n+1, sizeof(int));
for (int i = 0; i < n + 1; i++)
c[i] = (int*)calloc(m+ 1, sizeof(int)); //动态2维数组
cjs(n, m, c);
printf("%d\n", c[n][m]);
//输出
}
}
运行结果图：

算法分析：双重for循环，时间复杂度为O(n^2)。