## Number Triangles. Help me...

Moderator: Board moderators

### Number Triangles. Help me...

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.
ggggqqqqihc
New poster

Posts: 12
Joined: Sun Dec 07, 2003 10:45 am

DP

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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

Posts: 12
Joined: Sun Dec 07, 2003 10:45 am

ggggqqqqihc wrote: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.
windows2k
Experienced poster

Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Oh, I'm very sorry. The number triangles should be like
Code: Select all
`        3      2   8    2   6   0  8  2    5   22  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.
ggggqqqqihc
New poster

Posts: 12
Joined: Sun Dec 07, 2003 10:45 am

no, window2k was right
it is from USACO rite?
Kalo mau kaya, buat apa sekolah?
titid_gede
Experienced poster

Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

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.
ggggqqqqihc
New poster

Posts: 12
Joined: Sun Dec 07, 2003 10:45 am

ggggqqqqihc wrote: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
windows2k
Experienced poster

Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

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

Posts: 12
Joined: Sun Dec 07, 2003 10:45 am