Number Triangles

Algorithm:

Let p = [top node].
For each subsequent layer:
    Let new_p = []
    For each node:
        Look at the node's parents.
        If the node has one parent:
            Append node+sum to new_p.
        If the node has two parents:
            Append node+max(sums) to new_p.
    Let p = new_p.

Runs in linear time.

Python

def solve(rows):
    parents = [rows[0][0]]
    for row in rows[1:]:
        newParents = []
        ctr = 0
        for i in range(len(row)):
            # If node has one parent ...
            if i == 0:
                nodeParent = parents[0]
            elif i == len(row)-1:
                nodeParent = parents[-1] 
            else:
                nodeParent = max([parents[ctr],parents[ctr+1]])
                ctr += 1
            newParents.append(row[i] + nodeParent)
        print(parents)
        parents = newParents
    return max(parents)


def main():
    with open('numtri.in','r') as fIn:
        data = fIn.readlines()
        tree = [None] * int(data[0])
        print(data)
        for i in range(1,len(data[1:])+1):
            tree[i-1] = list(map(int,data[i].split()))
        print(tree)
    res = solve(tree)
    with open('numtri.out','w') as fOut:
        fOut.write(str(res)+'\n')

if __name__ == '__main__':
    main()

C++

#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
#include <iterator>

using namespace std;

void solve(vector<vector<int>> rows, int & ans){
    vector<int> parents(1);
    parents[0] = rows[0][0];
    rows.erase(rows.begin());
    for(auto row:rows){
        vector<int> newParents(row.size());
        int ctr = 0;
        for(int i=0; i<row.size(); ++i){
            int nodeParent;
            if(i==0){
                nodeParent = parents[0];
            }
            else if(i==row.size()-1){
                nodeParent = parents[parents.size()-1];
            }
            else{
                int a = parents[ctr];
                int b = parents[ctr+1];
                ctr ++;
                if(a>b){
                    nodeParent = a;
                }
                else{
                    nodeParent = b;
                }
            }
            newParents[i] = row[i] + nodeParent;
        }
        parents = newParents;
        for(auto i:parents){
            cout << i << " ";
        }
        cout << endl;
    }
    sort(parents.begin(),parents.end());
    ans = parents.back();
}

int main(){
    ifstream fIn ("numtri.in");
    string str;
    int numRows = 0;
    fIn >> numRows;
    vector<vector<int>> rowValues(numRows);
    for (int i = 0; i < numRows; ++i)
    {
        rowValues[i].resize(i + 1);
        for (int j = 0; j < i + 1; ++j)
        {
            fIn >> rowValues[i][j]; 
        }
    }
    fIn.close();

    int ans;
    solve(rowValues,ans);
    ofstream fOut ("numtri.out");
    fOut << ans << endl;
    fOut.close();
}