The best programs are written so that computing machines can perform
them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist
who works with traditional aesthetic and literary forms as well as mathematical concepts, to
communicate the way that an algorithm works and to convince a reader that the results will be correct.
― Donald E. Knuth

Problem :-
Given a triangle in the form of a lower diagonal matrix, find the weight of maximum path in the triangle.
Two possible branches for an element at matrix [ i ][ j ] are matrix [ i+1 ][ j ] & matrix [ i+1 ][ j+1 ].
Consider the triangle :-
2
2 1
3 2 4
5 6 8 6
Maximum weighted path is 2 (matrix[0][0]) + 1 (matrix[1][1]) + 4 (matrix[2][2]) + 8 (matrix[3][2]) = 15

Solution :-
At any cell ( i , j ) of the triangular matrix, we have two possible cells to choose [ ( i + 1 , j ) or ( i + 1 , j + 1 ) ]
We will consider both the options and recursively find out the weights obtained for the paths.
Finally, we return the maximum weighted path. See the implementation below.

#include<iostream>using namespace std;
int max(int a,int b) {
return (a > b ? a : b);
}
// compute the max weighted path in a bottom up approachint computeMaxPath(int triangle[4][4],int size,int i,int j) {
if(size-1 == i) {
// boundary case ( single cell matrix )return triangle[i][j];
}
else {
// find the max path from two possible branches
// considering triangle[i][j] as the rootint a = computeMaxPath(triangle,size,i+1,j);
int b = computeMaxPath(triangle,size,i+1,j+1);
return triangle[i][j] + max(a,b);
}
}
// mainint main() {
int triangle[4][4] = { {2,0,0,0},
{2,1,0,0},
{3,2,4,0},
{5,6,8,6} };
// max path = 2+1+4+8 = 15int size = 4;
// last 2 params denote the cell indices in the matrix int path_weight = computeMaxPath(triangle,size,0,0);
cout<<"\nPath Weight = "<<path_weight;
cout<<endl;
return 0;
}

#include<iostream>using namespace std;
int max(int a,int b) {
return (a > b ? a : b);
}
// compute the max weighted path in a bottom up approachint computeMaxPath(int triangle[4][4],int size,int i,int j) {
if(size-1 == i) {
// boundary case ( single cell matrix )return triangle[i][j];
}
else {
// find the max path from two possible branches
// considering triangle[i][j] as the rootint a = computeMaxPath(triangle,size,i+1,j);
int b = computeMaxPath(triangle,size,i+1,j+1);
return triangle[i][j] + max(a,b);
}
}
// mainint main() {
int triangle[4][4] = { {2,0,0,0},
{2,1,0,0},
{3,2,4,0},
{5,6,8,6} };
// max path = 2+1+4+8 = 15int size = 4;
// last 2 params denote the cell indices in the matrix int path_weight = computeMaxPath(triangle,size,0,0);
cout<<"\nPath Weight = "<<path_weight;
cout<<endl;
return 0;
}