三角形-题解(C语言代码)

#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
    if(a>b)return a;
    return b;
}
int main()
{
    int n;
    int k;
    int h;
    int i,j;
    int tri[200][200]={0};
    scanf("%d" , &n);
    for(i=1;i<=n;i++)
    {
        scanf("%d" , &h);
        for(k=1;k<=h;k++)
        for(j=1;j<=k;j++)               //将三角形数输入
        scanf("%d" , &tri[k][j]);
        for(k=h;k>=1;k--)
        {
            for(j=1;j<=k;j++)
            {
                tri[k][j]+=max(tri[k+1][j],tri[k+1][j+1]);       //状态转移方程：根据要求，从底层开始，每一层加和下一层的值并取局部最优解此时满足，局部最优解，即为全局最优解所以当进行取值到最顶层时，此时最顶层的解即为全局最优解
            }
        }
        printf("%d\n" , tri[1][1]);
        memset(tri,0,sizeof(tri));
    }
}