Старая загадка Top Coder: Получение числа путем вставки +

Я думаю о этой проблеме с топкодером .

Для данной строки цифр найдите минимальное количество добавлений, необходимых для того, чтобы строка равнялась некоторому целевому числу. Каждое добавление эквивалентно вставке знака плюса где-нибудь в строку цифр. После того, как все знаки плюса вставлены, вычислите сумму как обычно.

Например, рассмотрите «303» и целевую сумму 6. Лучшая стратегия - «3 + 03».

Я бы решил это грубой силой следующим образом:

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

Есть ли в этом смысл? Оптимально ли это с точки зрения производительности?

...

Что ж, теперь я вижу, что решение динамического программирования будет более эффективным. Однако интересно, имеет ли представленное решение в любом случае смысл.