三角数塔问题

[c]代码库

#include <stdio.h>
#include <stdlib.h>

#define MAXN 101

int n,d[MAXN][MAXN];
int a[MAXN][MAXN];

void fnRecursive(int,int);
//递推方法函数声明
int fnMemorySearch(int,int);
//记忆化搜索函数声明

int main()
{
    int i,j;
    printf("输入三角形的行数n(n=1-100):\n");
    scanf("%d",&n);
    printf("按行输入数字三角形上的数(1-100):\n");
    for(i=1; i<=n; i++)
        for(j=1; j<=i; j++)
            scanf("%d",&a[i][j]);
    for(i=1; i<=n; i++)
        for(j=1; j<=i; j++)
            d[i][j]=-1;//初始化指标数组
    printf("递推方法：1\n记忆化搜索方法：2\n");
    int select;
    scanf("%d",&select);
    if(select==1)
    {
        fnRecursive(i,j);//调用递推方法
        printf("\n%d\n",d[1][1]);
    }
    if(select==2)
    {
        printf("\n%d\n",fnMemorySearch(1,1));//调用记忆化搜索方法
    }
    else
        printf("输入错误！");

        return 0;
}

void fnRecursive(int i,int j)
//递推方法实现过程
{
    for(j=1; j<=n; j++)
        d[n][j]=a[n][j];
    for(i=n-1; i>=1; i--)
        for(j=1; j<=i; j++)
            d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]);
}

int fnMemorySearch(int i,int j)
//记忆化搜索实现过程
{
    if(d[i][j]>=0) return d[i][j];
    if(i==n) return(d[i][j]=a[i][j]);
    if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1))
        return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j)));
    else
        return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));
}