Comment by masfuerte

I had a similar idea iterating over the previously calculated sums. I implemented it in C# and it's a bit quicker taking about 78% of the time to run yours.

    int[] sums = new int[100000];
    for (int i = 9; i >= 0; --i)
    {
        sums[i] = i;
    }
    int level = 10;
    while (level < 100000)
    {
        for (int p = level - 1; p >= 0; --p)
        {
            int sum = sums[p];
            for (int i = 9; i > 0; --i)
            {
                sums[level * i + p] = i + sum;
            }
        }
        level *= 10;
    }