次のTopCoderの問題を解決しようとしています:
あなたは戦略ゲームをプレイしており、最後の戦いのために最強の軍隊を訓練したいと考えています。ゲームには N レベルのクリーチャーがあり、0 から N-1 までの番号が付けられています。あなたの軍隊にはすでにいくつかの生き物がいて、それらを訓練するのに D 日かかります。あなたが持っているクリーチャーの数は int[] カウントで与えられます。これには N 要素が含まれ、その i 番目の要素はレベル i のクリーチャーの数です。
毎日、1体のクリーチャーを選んで訓練することができます。訓練はクリーチャーのレベルを 1 上げる。つまり、レベル 0 のクリーチャーはレベル 1 のクリーチャーになり、レベル 1 のクリーチャーはレベル 2 のクリーチャーになる、などである。唯一の例外は、レベル N-1 のクリーチャーです。N-1 は可能な限り最大のレベルであるため、このようなクリーチャーは訓練できません。同じ生物を 1 日以上訓練することができます。たとえば、クリーチャーを 3 日間訓練すると、レベルが 3 上がります。日をスキップして、その日はクリーチャーを訓練しないこともできます。
あなたには int[] パワーが与えられます。パワーの i 番目の要素は、レベル i のクリーチャー 1 体のパワーです。あなたのアーミーのパワーは、そのすべてのクリーチャーのパワーの合計です。D 日間の訓練がすべて終了した後、あなたの軍隊が持つことができる最大のパワーを返します。
アルゴリズムを取得できません。これは動的プログラミングの問題であり、分割するのに適した副問題を見つけることができません。
問題を解決するために検討する必要がある副問題を誰かに教えてもらえますか?
また、解決策に至るまでの思考プロセスについても知りたいです。