[UVA] 10003 Cutting sticks

本來以為是單純的Huffman Encoding, WA! 因為Huffman Encoding只考慮棒子的長度，而題目有要求每根棒棒的起點需符合要求。這個陷阱搞了我三十分鍾，算是聰明反被聰明誤。

正確的作法是DP。想法如下：線段(x, y)的min cost可以表達成:
cost(x, y) = len(x, y) + min ( cost(x, z) + cost(z, y) ), where x < z < y。接下來，用2D array 建表即可 。唯一要注意的是diagonal DP的迴圈比較麻煩，第一次寫的時候犯了很多蠢錯。