USACO number triangle

Question

The question is as follows

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

        7

      3   8

    8   1   0

  2   7   4   4

4   5   2   6   5

In the sample above, the route 7 -> 3 -> 8 -> 7 -> 5 produces the highest sum: 30.

I had the following error

 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. 

My program works for the for the input <=8 triangle size. But, it fails for when triangle size is more than 8. why it is happening i don't know. please help.

Here is my code:

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

It works for the first 5 test cases but fails on 6th which has 199 triangle size.

Answer 1

Every time your program encounters a specific point in the pyramid, it calculates the optimum path to the bottom. However, you can make the observation that each point is encountered more than once, thus the optimum path is calculated several times. Therefore, your program runs in exponential time.

If you instead save the maxmimum sum achievable at some point in the triangle (here in dp[i][j]), and reuse that value instead of recomputing it once you hit that point again, your program will be much faster. That's because this algorithm only visits each point in the pyramid once. This is called top-down dynamic programming.

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