Number Triangles. Help me...

[ggggqqqqihc]

I am a beginner and I am learning search techniques. But there is a little difficult problem. I copied it:

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 from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.

PROGRAM NAME: numtri
INPUT FORMAT
The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.
SAMPLE INPUT (file numtri.in)
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

OUTPUT FORMAT
A single line containing the largest sum using the traversal specified.
SAMPLE OUTPUT (file numtri.out)
30

I want to use DFS but the number of lines may be too large. It may reach 1000! So I can't pass it. Is there any better algrithm to solve it?
Thank you very much.

[little joey]

DP

[ggggqqqqihc]

Could you give me more? It doesn't seem clear. How to use DP?

[windows2k]

Could you give me more? It doesn't seem clear. How to use DP?

C[i][j]=max(C[i-1][j],C[i-1][j-1])+s[i][j]
then find the largest number from C[n][1] to C[n][n] and output it
hope I don't misunderstand the meaning.

[ggggqqqqihc]

Oh, I'm very sorry. The number triangles should be like

Code: Select all

        3
      2   8
    2   6   0
  8  2    5   2
2  3   7    2   1

It means if the present number is 6, the next number must be 2 or 5. I think you misunderstood the meaning.

[titid_gede]

no, window2k was right
it is from USACO rite?

[ggggqqqqihc]

Yes, it is from USACO. But I don't know why C[i,j]=max(C[i-1,j],C[i-1,j-1])+s[i,j]. What's the meaning? Could you give me some code to explain it?

It is the last problem in Chapter 1, so I hope to solve it as soon as possible.

[windows2k]

Yes, it is from USACO. But I don't know why C[i,j]=max(C[i-1,j],C[i-1,j-1])+s[i,j]. What's the meaning? Could you give me some code to explain it?

It is the last problem in Chapter 1, so I hope to solve it as soon as possible.

here is my code

Code: Select all

#include <stdio.h>
int C[100][100],s[100][100],n;
int main()
{
   int max=0;
   scanf("%d",&n);
   for(int i=0;i<n;i++)
      for(int j=0;j<=i;j++)
         scanf("%d",&s[i][j]);
   for(int i=0;i<n;i++)
      for(int j=0;j<=i;j++)
      {
         C[i][j]=s[i][j];
         int t=0;
         if(i-1>=0) t=C[i-1][j];
         if(i-1>=0&&j-1>=0&&C[i-1][j-1]>t) t=C[i-1][j-1];
         C[i][j]+=t;
      }
   for(int i=0;i<n;i++)
      if(C[n-1][i]>max) max=C[n-1][i];
   printf("%d\n",max);
}


hope it helps

[ggggqqqqihc]

Although my compiler TCC find many mistakes. Thank you all the same.
I understand.