a bit of codechef: Sums in a Triangle

Problem Statement:
CodeChef: Sums in a Triangle

Summary:
Given a triangle with numbers on it, find the maximum weight path from top to bottom.

Solution:
This problem can be very overwhelming especially for a huge triangle such that a brute force solution (trying all different paths from top to bottom, and output the maximum weighted path) will take exponential time. Luckily, we can solve this problem efficiently using a concept called Dynamic Programming (DP).

Let's illustrate with the following triangle:
1
1 3
2 4 5
1 1 2 1

Let position \((i,j)\) denote \(i\)-th row and \(j\)-th column of the triangle, with topmost position is \((1,1)\). Furthermore, denote \(d(i,j)\) the value residing at position \((i,j)\).
It might not be immediately obvious which path to take, but suppose that we are at position \((i,j)\), and we know before hand the weight \(w(i+1,j)\), which is the maximum weight of the path starting from \((i+1,j)\) and also \(w(i,j+1)\), the maximum weight of the path starting from \((i,j+1)\). Then we can just choose whichever the highest, and follow that path to obtain the maximum weight path from our position \((i,j)\). Hence we can write:
$$ w(i,j) = max\{w(i+1,j),w(i,j+1)\} + d(i,j) $$

We have actually find a recursion to solve the problem! By using the optimal solutions from the subproblems, we construct an optimal solution for our current problem. If we implement the above recursion expression, we can solve the problem, but you'll notice that for large values, the algorithm can take very long to finish (and how long it is, it may take even years for large enough triangles). This is because a lot of time is spent to recalculate values that we already know, since many subproblems actually overlap. To avoid this, we can create a 2D array to store the values of \(w(i,j)\), and forces our algorithm to look up to this table and return its value whenever possible. If \(w(i,j)\) has already been calculated, we can just return the value. Only when \(w(i,j)\) has not yet been found that we explicitly proceed with the calculation, and update the value of \(w(i,j)\). Since the possible values of \((i,j)\) are only \(O(N^2)\), and each update only happens once throughout the completion of our algorithm, the running time of this top-down DP approach is \(O(N^2)\).

Another way to solve this problem is by a bottom-up approach: From the bottom of the triangles, we update the adjacent row immediately above it by explicitly choosing which  path we want to follow which maximize the weight, using the same recursive expression we have derived above. As an illustration, I'll show you step by step the updates on the triangle:
Initial:
1
1 3
2 4 5
1 1 2 1
First Update:
1
1 3
3 6 7
Second Update:
1
7 10
Last Update:
11

Hence maximum path will result in weight 11, and now the problem looks very simple! Bottom-up DP implementation usually are simpler, faster to code, and easier to debug than its twin top-down DP. However, top-down approach gives us a very intuitive and easy way to transform our recursive expressions into a more efficient algorithm. Note that this approach cannot be used on problems where subproblems are not overlapping, or the problem does not exhibit a optimal substructure characteristic.

A simple implementation of bottom-up DP for this problem is illustrated below:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int m[104][104];

int main(){
   int TC;
   scanf("%d",&TC);
      for(int T=0;T<TC;++T){
      int n;
      scanf("%d",&n);
      for(int i=0;i<n;++i){
         for(int j=0;j<=i;++j){
            scanf("%d",&m[i][j]);
         }
      }
      for(int i=n-2;i>=0;--i){
      for(int j=0;j<=i;++j){
            m[i][j]=max(m[i][j]+m[i+1][j],m[i][j]+m[i+1][j+1]);
         }
      }
      printf("%d\n",m[0][0]);
   }
   return 0;
}