C# – Finding lowest cost path – dynamic

I fail to see the need for dynamic programming. The following algorithm is O(n^2) in both time and space complexity (could be improved), but gets an exact answer--a significant improvement if you consider that dynamic programming is commonly used to solve problems with exponential complexity.

To start with, place every block on a graph that plots weight vs. height:

Next, create a directed graph based on the constraints of the problem (connections go from top-right to bottom left, by necessity):

Next, place all nodes with no incoming links into a queue (marked as green--Merry Christmas :) )

Simple breadth-first search (using your queue as the starting state) should allow you to find the longest path through the graph. The longest path represents the tallest tower possible. No worries about loops, as it is not possible given the constraints of the problem.

We can provide evidence of this algorithm's correctness by proving our initial step:

The base of the optimal tower will be represented by a node with no incoming links. Proof by contradiction: Assume the base node of an optimal tower has an incoming link. The incoming link implies that that node (and by necessity, the entire tower) could be placed on the node that is connected by the incoming node. This tower would be taller than the optimal tower--a contradiction, thus the original assumption must have been wrong.

Let me know if I missed a key point of the problem (or an edge case that is not solved by this method).

You want to store strings in compressed form (to save space, I guess), but you want fast lookup, is this right? If I were you, I would go for the speed and use a trie (for the first few characters). It has O(log n) lookup, and it will automatically condense common prefixes.

A lot depends on the statistics of the strings, like how many there are, and their typical length.

ADDED: For the strings you gave, the trie would look like this:

- A B - 1 2 3 4 5 - 6 .
  |     |           |
  |     |           7 .
  |     |           
  |     C D E F G - H .
  |                 |
  |                 X 1 .
  |                 |
  |                 Y .
  |
  X X X X .

Each node of the trie contains a little "dictionary" of "words", initially 1 letter long, and each "word" points to a sub-node. If that sub-node contains only one "word" in its own "dictionary", then that "word" can be absorbed into its parent's "word", and that's how you build up the prefixes.