Sums in a triangle

general
1

i cant understand the algorithm of this problem…
can anybody help me plz…

2

It is a standard dynamic programming question. Let’s move with very basic why we can apply dp here and why we should go for that option. For applying dp, we need two properties to be satisfied:

Optimal substructure: Lets say, we need to move to the index (i,j). We can move to this via (i-1,j) or (i-1,j-1). For getting maximum sum at (i,j), we want sum to be maximum of the path we’ll come through.
That is, if we know which of the paths via (i-1,j) or (i-1,j-1) is maximum, we’ll go through that cell.
Thus, if,

sum[i][j]= a[i][j]+ max(sum[i-1][j], sum[i-1][j-1]); // the two arguments in the max function represent the maximum cost of reaching to cells, [i-1][j] or [i-1][j-1]. Thus, if we know, solution to subproblems, we can get an optimal solution to our main problem.

Overlapping subproblems: Again, lets say we have to reach at index (1,4)

           [4,4]
          /    \
    [3,4]      [3,3]
    /   \       /  \
 `[2,4] [2,3]  [2,3] [2,2]`

// See here the subproblems overlap and hence we can apply dp.

Let us consider a 2-d matrix sum[i][j] which represents the maximum sum to reach the cell (i,j).

Thus, sum[i][j]= a[i][j]+ max(sum[i-1][j], sum[i-1][j-1]);

Thus we can write the following recursive solution:

int find(int i,int j)
{
  if(i<0 || j<0) return 0;
  if(i==0 && j==0)
    return a[0][0];
  if(i==1 && j==0) 
    return a[1][0];

  return a[i][j] + max(find(i-1,j), find(i,j-1));
}

We can now see, many problems are computed again and again, thus we can add memoization to it:

int find(int i, int j)
{
   if(i<0 || j<0)
     return 0;
   if(sum[i][j]!=-1)
   return sum[i][j];

   else
    sum[i][j]= a[i][j]+ max(find(i-1,j), find (i-1,j-1));
    return sum[i][j];
}

Refer to a very similar problem here.

1 Like
3

PS: some constraints in the above code may be missing, like checking for some (i,j) condition when one is less than 0 or so i.e.base checks. You can do that yourself, however, I don’t think any is missing. Also, mark the answer as accepted and close the thread after it satisfies you, it helps avoiding ambiguity, redundancy, also other learners to know the accurate results:) Happy to help…