一、数字三角形

二、我的代码

#include<stdio.h>
#include<malloc.h>
/*
6
2
96 30
83 52 60
21 65 44 61
8 79 50 41 21
61 41 50 38 79 10
*/
int max(int a, int b);

int main()
{
    int n;
    int** gold;
    int i, j;
    while(scanf("%d", &n) != EOF)
    {
        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]);
            }
        }
        //从底层往上层数，每个节点积累下两节点的最大值
        for (i = n - 2; i >= 0; i--)
        {
            for(j = 0; j < i + 1; j++)
            {
                gold[i][j] = gold[i][j] + max(gold[i + 1][j], gold[i + 1][j + 1]);
            }
        }
        printf("%d\n", gold[0][0]);

    }

    return 0;
}
int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

三、报错信息

题目要求处理一个近1000行的数字三角形，结果需要1000ms之内输出来，
但我的代码却要1200ms左右。
请问：我的代码有没有还可以优化的地方，加快运行时间？

#include <iostream>
#define Max 1005

using namespace std;

int n;
int a[Max][Max]={0}, dp[Max][Max]={0};

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=i; j++)
        cin >> a[i][j];
    }
    for(int i=n; i>=1; i--)
    {
        for(int j=1; j<=i; j++)
        {
            dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
        }
    }
    cout << dp[1][1] << endl;
    return 0;
}

一般来讲循环1E8次才会耗时1000ms以上，1000行算上输入和计算也就循环1E6次，1000ms完全够用了，应该不是算法的问题。

max改成内联，或者一开始分配一大块内存((int*) malloc(sizeof(int) * n*n))试试。
申请的内存最好用free释放掉。