Estoy pensando sobreeste problema de topcoder.

Dado una cadena de dígitos, encuentre el número mínimo de adiciones requeridas para que la cadena sea igual a algún número objetivo. Cada adición es el equivalente a insertar un signo más en algún lugar de la cadena de dígitos. Después de insertar todos los signos más, evalúe la suma como de costumbre.

Por ejemplo, considere "303" y una suma objetivo de 6. La mejor estrategia es "3 + 03".

Lo resolvería con fuerza bruta de la siguiente manera:

for each i in 0 to 9 // i -- number of plus signs to insert
  for each combination c of i from 10
    for each pos in c // we can just split the string w/o inserting plus signs
      insert plus sign in position pos 
    evaluate the expression
    if the expression value == given sum
      return i

¿Tiene sentido? ¿Es óptimo desde el punto de vista del rendimiento?

...

Bueno, ahora veo que una solución de programación dinámica será más eficiente. Sin embargo, es interesante si la solución presentada tiene sentido de todos modos.