数字三角形问题，时间超限，还不够快，有更快的方法吗？

Z时代
2024-01-10
分类：技术分享

一、数字三角形

图片说明

二、我的代码

#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;
}