#### Miscellaneous

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 approach
int 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 root
int a = computeMaxPath(triangle,size,i+1,j);
int b = computeMaxPath(triangle,size,i+1,j+1);
return triangle[i][j] + max(a,b);
}
}

// main
int 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 = 15
int 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;
}