動的計画法と離散最適化の問題

最近トップコーダーの問にまた苦労した。今回は建物の高さを計算するアルゴリズムでした。動的計画法は無理そうだったけど幅優先探索で出来るかもしれません。しかしこれもダメでした。結局動画的計画法を使用しました。The breadth-first search, if executed correctly, is untenable, as, in each layer, all possible splits (including not to split) need to be checked, leading to an exponential number of possible layers (say 10^8 if the value at each node in the fourth layer from the top is 20 and half of all values are searched for each node).
正解は深さ優先探索でした。 Using depth-first search with memorization (also considered dynamic programming), the complexity is reduced to only 100*100 writes to the 2-dimensional array　times 50*50 splits of N and K per write. While this results in a complexity of 25*10^6, which is somewhat large, the actual complexity is probably more like 25*25*100*100, which is a tractable 6.25*10^6.