Growing penetration of plug-in hybrid electric vehicles (PHEVs) places significant impacts on grid, either as electric loads or potential valued vehicle-to-grid (V2G) services. This paper proposes an optimisation strategy to recharge PHEVs batteries with minimum charging cost as well as to produce desired power for grid frequency regulation. The cost arising from the battery charging and the revenue obtained by providing regulation are investigated and represented mathematically. Dynamic programming (DP) algorithm is applied to construct the problem and to compute the optimal controlling strategy for a fleet of PHEVs. Battery state-of-charge (SoC) and charging current are taken as the state factor and control factor of the objective function. Driving energy demand and regulation requirements are treated as disturbances in objective function. Pricing data in cost function and load data in objective function are original from PJM. Simulations are provided to illustrate the optimality of the proposed strategy in 24 hours with variations of parameters.