Dynamic programming algorithms: try Pass Triangle from Code Eval

Hi,

A close friend of mine sent a tweet a few days ago announcing:

I have solved some challenge at Code Eval…

Since I was preparing for my algorithms final, I decided to give Code Eval a try to review various algorithms I’ve learned in class.

How it works: Code Eval (www.codeeval.com) let’s you submit solutions to various challenges in your favorite language (for me, C++ and Python). Once you submit your solution, it’ll score your output, and if you solve it, gives you an opportunity to tweet about it. The aim of the site is to connect programmers and companies, as part of this purpose, Code Eval lists “package problems” where a company sponsors a challenge (some are easy, others are hard).

Now why do I mention the Pass Triangle challenge from Code Eval? Because it helped me understand what dynamic programming algorithms are and how they work. Dynamic programming allows building the solution to a problem by computing answers to subproblems. This is done by filling out a table based on a defined pattern, or it is called “recurrence relation.” Effectively, when you’re solving problems involving dynamic programming, you’re solving this recurrence relation.

The pass triangle challenge can be found at:

https://www.codeeval.com/public_sc/89/

Here, one would be tempted to start with greedy choice, since you can add sums for each level and choose the maximum of two subtrees. But this will not work, hence dynamic programming is the way to go (you would fill out a solutions table, then choose the max once you’re done with the entire tree of numbers).

Good luck.