hi i have been working on sums in triangle problem
i don’t want to see the solutions
i just want to know the basic approach behind it so that i can solve it myself
please tell me how should i approach this problem
This should help you
It is said you need to start at the top of the triangle (where there is only one number) and keep moving to the number directly below or to the right until you reach the last row…
Take as an example the triangle:
1
1 2
9 2 3
If you want to maximize the sum by only moving right or down, is it clear to you that you should follow the path 1 -> 1 -> 9?
Note that 1 is not the maximum number you can choose on the 2nd row, but, it is the number that will “give you acess” to the number 9 on the third row, number which you will need to use if you want to reach the maximum sum…
This idea probably could lead us to use some sort of depth-first search and/or recursion… It turns out that for a triangle with as many rows as 100, there are 2^99 routes altogether… That would take you some billion years to check all of them if you could check one trillion of routes per second!!
So, we already know it would be good if we somehow knew in advance that we need to use number 9 on our solution without checking all possible routes… That can be done by using a bottom up approach instead of a top down one…
Let’s list all the possible sums we can make with the last 2 rows (I am starting from right to left here):
using the 3 and 2 on last row we can have:
3+2 or 2+2 (summing them with the 2 on 2nd row, as it directly above or one place to the right);
Using the 9 and the 2 we get:
2+1 or 9+1
So, as you see two interesting things happened:
We used the same number (2) twice (one time for each of the 2 neighbouring numbers on the same row) and we also managed to obtain all 4 results:
5 or 4 for the 1st pair
3 or 10 for the 2nd pair
This suggests that as we are using some values to repeat calculations, we can use recursion with memoization to solve the problem fast, and that’s what we will do up to a point, let’s see:
We now know that the 2 maximum values we can obtain from the last rows are 5 and 10, so we replace these values on second row, and eliminate the third one completely, to get the new triangle:
1
10 5
From here, it’s easy to see that the maximum sum is 11.
This approach works because we actually follow a down or to the right approach as required… Instead of starting at the top and waste all the time computing useless sums, by starting at the bottom and storing the maximum values we are “implicitly” removing lots of unnecessary values…
Hope I could help,
Bruno
27 Likes
thanks alot @kuruma for giving so much time for this problem and helping me with such a nice and simple illustration
i now managed to solve it successfully
thanks alot
1 Like
can anyone help pls. ideone accepts my answer; however, i am getting TLE answer from codechef for my c++ solution: AhNRnV - Online C++ Compiler & Debugging Tool - Ideone.com
#include <iostream>
using namespace std;
int main() {
// your code goes here
int a, b, arr[98][98]={0}, i, j, count=0, i_temp, j_temp, max, max1, max2;
cin>>a;
while(a--) {
arr[98][98]=0;
cin>>b;
count=0;
for(i=0; i<b; i++) {
if(count<b) count++;
for(j=0; j<count; j++) {
cin>>arr[i][j];
}
}
i_temp=i, j_temp=j;
for(; i>0; i--) {
j=j_temp;
for(; j>0; j--) {
max1=arr[i][j-1]+arr[i-1][j-1], max2=arr[i][j]+arr[i-1][j-1];
if(max1>max2) max=max1; else max=max2;
arr[i-1][j-1]=max;
}
j_temp=j_temp-1;
}
cout<<arr[0][0]<<endl;
//arr[100][100]=0;
}
return 0;
}
@kuruma,
@garakchy,
@bugkiller, @junior94, @vineetpaliwal, @anton_lunyov, @betlista, @cyberax
i have implemented a top-bottom approach , verified may test cases but still i get wa
# include <iostream>
# include <stdio.h>
# include <math.h>
# include <list>
# include <algorithm>
typedef long long int LL;
using namespace std;
LL arr[99][99], val_arr[99][99]={0};
LL value (int x,int y){
if((!arr[x-1][y])&&(!arr[x-1][y-1])){
return arr[x][y];
}
else if ((!arr[x-1][y])){
return (arr[x][y]+val_arr[x-1][y-1]);
}
else if ((!arr[x-1][y-1])){
return (arr[x][y]+val_arr[x-1][y]);
}
else{
return ( val_arr[x-1][y-1]>=val_arr[x-1][y]? (arr[x][y]+val_arr[x-1][y-1]):(arr[x][y]+val_arr[x-1][y]) );
}
}
int main(){
int t;
scanf("%d",&t);
for(int i=0; i<t; i++){
int n;
scanf("%d",&n);
for(int j=0; j<n; j++){
for(int k=0; k<=j; k++){
scanf("%lld",&arr[j][k]);
val_arr[j][k]=value(j,k);
}
}
LL ans=-1;
for(int j=0; j<n; j++){
if(val_arr[n-1][j]>ans){
ans=val_arr[n-1][j];
}
}
printf("%lld\n", ans);
}
}
Those looking for Top Bottom approach (not the fast one).
I solved this problem using top-bottom approach first. Got TLE. Didn’t want it to go waste, thus sharing it.
#include<iostream>
#include<cmath>
using namespace std;
int t,n,i;
short inp[5050] = {};
int sum_trian(int row,int column,int parent) {
int index = ( (row-1)*row ) / 2 + column - 1;
if( row==n )
return (parent+inp[index]);
parent += inp[index];
return max(sum_trian(row+1,column,parent), sum_trian(row+1,column+1,parent));
}
int main() {
cin >> t;
while(t>0) {
cin >> n;
for(i=0;i<(n*(n+1)/2);i++)
cin>>inp[i];
cout << sum_trian(1,1,0) << endl;
t--;
}
return 0;
}
1 Like
#include <stdio.h>
int sumtria(int a[][100],int n,int p,int q);
int max(int a,int b);
int main()
{
int n,t,a[100][100],cost,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<=i;j++)
scanf("%d",&a[i][j]);
cost=sumtria(a,n,0,0);
printf("%d",cost);
printf("\n");
}
return 0;
}
int sumtria(int a[][100],int n,int p,int q)
{
int cost;
if(p==n-1)
return a[p][q];
else
cost=a[p][q]+(max((sumtria(a,n,p+1,q)),(sumtria(a,n,p+1,q+1))));
return cost;
}
int max(int d,int b)
{
if(d>b)
return d;
else
return b;
}
its a recursive approach still i get TLE error plz help me to modify my code so to get it AC
1 Like
i have the same problem in understanding the logic as mentioned by dabbcomputers
i guess it will not work correctly in that case
Hello @nishant_25,
It is my pleasure to help anyone who needs some help This community has given me much more than I could have ever asked for, including new friends, new problem-solving skills and even the chance to set my own problems so that the best coders in the world can solve them :))
So, stick around, it’s worth so, so much 
PS: If you want to know, after seeing your submission, I was able to understand how I could build an array to store the triangle in C++, so THANK YOU as well
3 Likes
ha ha
so i also helped you
its kinda funny
2 Likes
Very nicely explained. Thanks a ton! Dynamic Programming is proving tricky to master. I must’ve read a dozen tutorials already.
1 Like
Hello @niharika1k29_9,
It’s a pleasure to help!! I am glad you liked my post and I’m also learning it myself!! The more tutorials and/or editorials you read, the more you’ll learn 
I wish you the best of luck
One of the best explained analogy . Very easy to understand .Nice work ! Thanks a lot
1 Like
Thank you very much!!!
Your acknowledgement means a lot to me
Best regards,
Bruno
you can avoid initializing arr[98][98] to 0 apart from that i think everything is Ok
Awesome :)…But i had to look up at your solution too also for implementation of your algorithm.
Thank you very much! Very good explanation