動的計画法とゲーム理論

最近コードシェッフと言うシステム開発試合に苦労しました。一つな問いはゲーム木の検索に関わる問題でした。　Using a standard memoization, I encountered no incorrect results, but the performance, even for the intermediate cases, was too slow. I could at least complete the intermediate cases using a dynamic programming approach with a "bestfrom" cache based on start index and move number, but this generated an incorrect answer in the simple case. でも僕が作った入力データは全部正しい出力になりました。やっぱりちょっと意外な動作を考えなければ行けないと解けません。The subtle point I had missed was that, while I was careful to check that the "bestFrom" array, which indicated the best sum possible starting from or after an index in a given move was not overstating the value by caching an index beyond the allowed start range, I forgot that it might underestimate the value by caching a sum from a previous visit when the right bound on the start index was much lower.
I found no general dynamic programming solution. Only a memoization solution which is too slow for the larger cases (beyond easy) and a dynamic-programming approach used only when M==2 (the medium test case constraint). Thus, the hard cases were left as timed-out.