我想知道是否有人可以帮助我尝试解决这个问题。
我想f(str)取一串str数字并将所有子串的总和作为数字返回，我想把它写成f一个函数，这样我就可以尝试通过记忆来解决这个问题。
当我凝视时，它并没有向我跳跃
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
你必须分解f成两个功能。
让N[i]成为i输入的第 th 位数字。让T[i]是i-1输入的第一个字符的子串的总和。让B[i]是i输入的第一个字符的后缀之和。
因此，如果输入是“12395”，则B[3] = 9+39+239+1239, 和T[3] = 123+12+23+1+2+3。
递推关系为：
T[0] = B[0] = 0
T[i+1] = T[i] + B[i]
B[i+1] = B[i]*10 + (i+1)*N[i]
最后一行需要解释：第一的后缀i+2字符是所述第一的后缀i+1以字符N[i]所附上的端，以及所述单个字符的字符串N[i]。这些的总和(B[i]*10+N[i]*i) + N[i]与 相同B[i]*10+N[i]*(i+1)。
还有f(N) = T[len(N)] + B[len(N)]。
这给出了一个简短的、线性时间的、迭代的解决方案，您可以将其视为一个动态程序：
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")
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句