RPG Math - Problem 8 (Now With More Combat Action!)

This problem isn't based on a role-playing game, but rather on a tabletop wargame, but it is still too good to pass up.

The game this problem is based on is Warmachine. Warmachine is a wargame in the same vein as Warhammer Fantrasy or Warhammer 40k, where you have miniatures that you move around on a board measuring distances rather than on a square or hex grid. However, Warmachine has several features that make it so I like it more than those other games:

1. There are fewer models you have to put together to form a decent army, and each model has fewer pieces.

2. There is more variety in units - each different type of unit has unique special powers. This makes the game much more interesting and more strategic because you have to look at what the opponent has brought to the table (you are allowed to look at the "stat cards" that have the opponents' units' stats and powers on them) and figure out how best to counter their powers with your own. Also there is more strategy in army selection as you try to put together an army that has powers that complement each other. For example one very useful combo is the "Bile Thrall", which applies a "corrosion" effect to targets it hits with its Bile Cannon, combined with the "Cankerworm," a large worm-shaped "warjack" (i.e. battle robot) which has an Ablation ability that allows it to ignore half the target's armor when it hits an enemy unit that has corrosion on it. In one game I successfully used this combo to kill an enemy warjack in one turn that was so heavily armored it would have been very difficult to kill any other way. Unfortunately I then made a tactical blunder: I left my "warcaster" (the army's leader) exposed in a place where the enemy could use one of his last remaining units to charge and kill him.

Anyway this is an RPG Math post so let's get right to the puzzle:

Problem 8: "Focus Fire!"

In Warmachine, there are some units (like squads of infantry) that are composed of lots of identical models. Some of these units have the "Combined Melee Attack" or "Combined Ranged Attack" special ability. This special ability allows the unit to, rather than having each model in the unit attack separately and make separate attack and damage rolls, combine several models' attacks into one attack with bonuses to the attack and damage rolls.

When using combined attacks, the player can choose how to group the models into attacks. For example, if a unit had 8 models, the player could choose to make 8 separate attacks, to make one attack that combined all 8 models, to make two attacks using 3 models each and one attack using the remaining 2 models, etc.

Assume that the unit has N models, and the player's goal is to maximize the total expected amount of damage done to the target. Let F(x) be the expected damage done from one attack with x models. Suppose you are given the values of F(x) for each value of x between 1 and N inclusive. Find a polynomial-time algorithm* to compute the best possible grouping.

Hint: Let G_i(j) be the best possible expected damage using j models in groups of no more than i each. Think about how to calculate the values of G_i if you already know the values of G_(i-1).

The solution is here.

*This means that the running time of the algorithm is bounded by A(n^B) for some constants A and B.