c - USACO 数字三角形

Question

问题如下

考虑下面显示的数字三角形。编写一个程序，计算从顶部开始到底部某处结束的路线上可以传递的最大数字总和。每一步都可以向左斜向下或向右斜向下。

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

在上面的示例中，路线 7 -> 3 -> 8 -> 7 -> 5 产生最高总和:30。

我有以下错误

 Execution error: Your program (`numtri') used more than the
    allotted runtime of 1 seconds (it ended or was stopped at 1.674
    seconds) when presented with test case 6. It used 6080 KB of
    memory. 

我的程序适用于输入 <=8 的三角形大小。但是，当三角形大小超过 8 时，它会失败。我不知道为什么会这样。请帮忙。

这是我的代码:

#define MAX 1000

int max=0,a[MAX][MAX];

void dfs(int i,int j,int end,int sum)
{
 if(i<=end)
 {   
      sum += a[i][j];
      dfs(i+1,j,end,sum);
      dfs(i+1,j+1,end,sum);
 }
 else 
 {
      if(sum>max)  
      max = sum;

 }
}

int main () {

FILE *fin  = fopen ("numtri.in", "r");
FILE *fout = fopen ("numtri.out", "w");
int r,i,j;

fscanf(fin,"%d",&r);

for(i = 1;i<=r;i++)
 for(j = 1;j<=i;j++)
  fscanf(fin,"%d",&a[i][j]);

dfs(1,1,r,0);

fprintf(fout,"%d\n",max);

fclose(fin);
fclose(fout);
return 0;
}

它适用于前 5 个测试用例，但在三角形大小为 199 的第 6 个测试用例中失败。

Answer 1

每次您的程序遇到金字塔中的特定点时，它都会计算到达底部的最佳路径。但是，您可以观察到每个点都会遇到不止一次，因此最佳路径会被多次计算。因此，您的程序以指数时间运行。

如果您改为保存三角形中某个点可实现的最大总和(此处为 dp[i][j])，并重用该值而不是在您再次到达该点时重新计算它，你的程序会快得多。那是因为该算法只访问金字塔中的每个点一次。这称为自上而下的动态规划。

#include<string.h>
#include<stdio.h>
#define MAX_N 1005

int a[MAX_N][MAX_N];
int dp[MAX_N][MAX_N];

int max(int a, int b)
{
  return a > b ? a : b;
}

int dfs(int i,int j,int end)
{
  if(dp[i][j] != -1)
  {
    return dp[i][j];
  }
  else if(i <= end)
  {
    return dp[i][j] = a[i][j] + max(dfs(i+1,j,end), dfs(i+1,j+1,end));
  }
  else
  {
    return 0;
  }
}

int main () {
  FILE *fin  = fopen ("numtri.in", "r");
  FILE *fout = fopen ("numtri.out", "w");
  int r,i,j;

  memset(dp, -1, sizeof dp);

  fscanf(fin,"%d",&r);

  for(i = 1;i<=r;i++)
    for(j = 1;j<=i;j++)
      fscanf(fin,"%d",&a[i][j]);

  fprintf(fout,"%d\n", dfs(1,1,r));

  fclose(fin);
  fclose(fout);
  return 0;
}