title: Creature training Dynamic Programming on TopCoder
body: <p>I have been trying to solve <a href="http://community.topcoder.com/stat?c=problem_statement&amp;pm=8570&amp;rd=12012&amp;rm=269199&amp;cr=7581406" rel="nofollow noreferrer">the following TopCoder problem</a>:</p>
  <blockquote>
  <p>You are playing a strategy game and you wish to train the strongest army for the final fight. There are creatures of N levels in the game, numbered from 0 to N-1, inclusive. You already have some creatures in your army and D days to train them. The number of creatures you have is given in a int[] count. It contains N elements and its i-th element is the number of creatures of level i.</p>
  <p>During each day, you can choose one creature and train it. Training increases a creature's level by 1, i.e., a creature of level 0 becomes a creature of level 1, a creature of level 1 becomes a creature of level 2, and so on. The only exception is creatures of level N-1 - such creatures can't be trained as N-1 is the largest possible level. You can train the same creature during more than one day. For example, if you train a creature during 3 days, it will gain 3 levels. You can also skip days and not train any creatures during those days.</p>
  <p>You are given a int[] power, where the i-th element of power is the power of one creature of level i. The power of your army is the sum of the powers of all its creatures. Return the maximum possible power your army can have after all D days of training are finished.</p>
  </blockquote>
  <p>I'm not able to get the algorithm. It is a Dynamic Programming problem and I'm not able to find any suitable subproblem to which to break it to.</p>
  <p>Can anyone provide me with the subproblem I need to consider to solve the problem?</p>
  <p>I'd also like to know about the thinking process by which you arrive at the solution.</p>