How to write a function f("123")=123+12+23+1+2+3 as a recurrence relationship

Question

I'm wondering if someone can help me try to figure this out.

I want f(str) to take a string str of digits and return the sum of all substrings as numbers, and I want to write f as a function of itself so that I can try to solve this with memoization.

It's not jumping out at me as I stare at

        Solve("1") = 1
        Solve("2") = 2
        Solve("12") = 12 + 1 + 2
        Solve("29") = 29 + 2 + 9
        Solve("129") = 129 + 12 + 29 + 1 + 2 + 9
        Solve("293") = 293 + 29 + 93 + 2 + 9 + 3
        Solve("1293") = 1293 + 129 + 293 + 12 + 29 + 93 + 1 + 2 + 9 + 3
        Solve("2395") = 2395 + 239 + 395 + 23 + 39 + 95 + 2 + 3 + 9 + 5
        Solve("12395") = 12395 + 1239 + 2395 + 123 + 239 + 395 + 12 + 23 + 39 + 95 + 1 + 2 + 3 + 9 + 5

Answer 1

You have to break f down into two functions.

Let N[i] be the ith digit of the input. Let T[i] be the sum of substrings of the first i-1 characters of the input. Let B[i] be the sum of suffixes of the first i characters of the input.

So if the input is "12395", then B[3] = 9+39+239+1239, and T[3] = 123+12+23+1+2+3.

The recurrence relations are:

T[0] = B[0] = 0
T[i+1] = T[i] + B[i]
B[i+1] = B[i]*10 + (i+1)*N[i]

The last line needs some explanation: the suffixes of the first i+2 characters are the suffixes of the first i+1 characters with the N[i] appended on the end, as well as the single-character string N[i]. The sum of these is (B[i]*10+N[i]*i) + N[i] which is the same as B[i]*10+N[i]*(i+1).

Also f(N) = T[len(N)] + B[len(N)].

This gives a short, linear-time, iterative solution, which you could consider to be a dynamic program:

def solve(n):
    rt, rb = 0, 0
    for i in xrange(len(n)):
        rt, rb = rt+rb, rb*10+(i+1)*int(n[i])
    return rt+rb

print solve("12395")