トップコーダーで問題を解決していたところ、DP の問題に遭遇しました ( http://goo.gl/hjeaS )
これには効率的な dp ソリューションが必要ですが、行き詰まっています。サブの問題を保存するために配列 res[i][j][k] を取りましたが、実行、特に細かい部分がわかりません。
r[i][j][k] は最小数を格納します。合計 k を得るために、i と j の間に挿入されるプラス記号の数。そのため、i、j、k をループして、i と j の間のすべての場所にプラス記号を挿入しました。最小値は、すべての要素 i から j (特定の合計 k について) をループした後に取得されます。ただし、配列の初期値と制限がどうあるべきかについてはわかりません。より効率的な解決策はありますか? (私のは O(n³k) のようです)
PS別の同様の質問があることは知っていますが、問題に対するdpソリューションの背後にあるロジック/コードを実際に説明している回答はありません。