用记忆化递归DP求解Sam and substrings问题遇运行时错误求排查

问题概述 #

给定一个无前导零的数字字符串，计算其所有子串对应的整数值之和，结果需对 (10^9+7) 取模。例如输入"42"，子串为4、2、42，总和为48，取模后结果为48。

你的两种递归实现 #

自顶向下版本 #

from functools import cache

def substrings(n):
    @cache
    def substrSum(curIndex):
        if curIndex == 0: return int(n[0])
        return substrSum(curIndex-1)*10 + int(n[curIndex]) * (curIndex+1)
        
    totalSum = 0
    for i in range(len(n)-1, -1,-1): 
        totalSum += substrSum(i) 
        
    return totalSum % (10 ** 9 + 7) 

自底向上版本（调整循环方向） #

from functools import cache

def substrings(n):
    @cache
    def substrSum(curIndex):
        if curIndex == 0: return int(n[0])
        return substrSum(curIndex-1)*10 + int(n[curIndex]) * (curIndex+1)
        
    totalSum = 0
    for i in range(len(n)): 
        totalSum += substrSum(i) 
        
    return totalSum % (10 ** 9 + 7) 

错误根源 #

1. 递归栈溢出：HackerRank的测试用例包含超长字符串（比如长度达10^5），而Python默认递归深度限制在1000左右。当递归调用深度超过这个限制时，会直接触发RecursionError，这是运行时错误的主要原因。
2. 中间数值过大：递归过程中计算的中间值会指数级增长，即使有记忆化，也会导致内存占用过高、计算速度变慢，进一步加剧运行时问题。

修正方案：迭代式动态规划 #

用迭代代替递归，彻底避免栈溢出问题，同时每一步都对中间结果取模，控制数值大小：

MOD = 10**9 + 7

def substrings(n):
    total = 0
    prev_sum = 0
    for idx in range(len(n)):
        digit = int(n[idx])
        # 计算以当前位置结尾的所有子串的和
        current_sum = (prev_sum * 10 + digit * (idx + 1)) % MOD
        total = (total + current_sum) % MOD
        prev_sum = current_sum
    return total

逻辑说明 #

• prev_sum保存到前一个位置为止，所有以该位置结尾的子串的总和
• 对于第idx位的数字digit，以它结尾的子串包括：单独的digit，以及前面所有子串后拼接digit（即每个前面的子串数值*10 + digit），因此总和为prev_sum*10 + digit*(idx+1)（idx+1是因为digit在个位总共出现了idx+1次）
• 每一步对current_sum和total取模，既避免数值过大，又保证结果正确性

示例验证 #

输入"42"：

• 第0位（digit=4）：current_sum=4*(0+1)=4，total=4，prev_sum=4
• 第1位（digit=2）：current_sum=4*10 +2*(1+1)=44，total=4+44=48，返回48%MOD=48，与示例结果一致。

内容的提问来源于stack exchange，提问作者Rnj