Eu estou pensando sobre este problema do codificador top.

Dada uma sequência de dígitos, encontre o número mínimo de adições necessárias para que a sequência seja igual a um número de destino. Cada adição é o equivalente a inserir um sinal de mais em algum lugar na sequência de dígitos. Depois que todos os sinais de adição forem inseridos, avalie a soma como de costum

Por exemplo, considere "303" e uma soma alvo de 6. A melhor estratégia é "3 + 03"

Eu o resolveria com força bruta da seguinte forma:

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

Isso faz sentido? É ideal do ponto de vista do desempenho?

...

Bem, agora vejo que uma solução de programação dinâmica será mais eficiente. No entanto, é interessante que a solução apresentada faça sentido de qualquer maneir