数字三角形问题，编程结果是时间超限，求解决

Question

一、数字三角形问题

二、我的代码 （可运行，但太久）

#include<stdio.h>
#include<malloc.h>


void Get_Max(int **gold, int n, int pos_row, int pos_col, int sum, int *max);

int main()
{
    int n;
    int** gold;
    int max;
    int i, j;
    while(scanf("%d", &n) != EOF)
    {
        max = 0;
        gold = (int**) malloc(sizeof(int*) * n);
        for(i = 0; i < n; i++)
        {
            gold[i] = (int*) malloc(sizeof(int) * (i + 1));
            for(j = 0; j < i + 1; j++)
            {
                scanf("%d", &gold[i][j]);
            }
        }
        Get_Max(gold, n, 0, 0, 0, &max);
        printf("%d\n", max);
    }

    return 0;
}
//迭代累加金币，得出最大值
void Get_Max(int **gold, int n, int pos_row, int pos_col, int sum, int *max)
{   
    //还未到底时继续走
    if(pos_row < n)         
    {
        //累加每步的数值
        sum += gold[pos_row][pos_col];
        //往下走
        Get_Max(gold, n, pos_row + 1, pos_col, sum, max);   
        //往右下走
        Get_Max(gold, n, pos_row + 1, pos_col + 1, sum, max);   
    }
    else        
    {
        //走到底时，最大的总和存储起来
        if(sum > *max)
            *max = sum;
    }
}

三、报错信息

时间要限制在1s以内

Answer 1

从底层向上走，动态规划，伪码如下：

// A行B列
// array为输入的数据
for i in range(A-2,0):
    for j in range(0,i):
            array[i,j] = max(array[i+1,j],array[i+1,j+1])
// 最后结果取array[0,0]