使用动态规划求所有整数子串的总和

Question

我正在解决 hackerrank 的 Sam 和子串问题。它基本上是查找具有所有整数的字符串的所有子字符串的总和。

萨曼莎和山姆正在玩数字游戏。给定一个数字作为字符串，没有前导零，确定该字符串的子字符串的所有整数值的总和。

给定一个字符串形式的整数，将其所有转换为整数的子字符串相加。由于数字可能会变大，因此返回模 10⁹ + 7 的值。

示例：

n = '42'

这里 n 是一个字符串，它具有三个整数子字符串：4、2 和 42。它们的和是 48，48 模 10⁹ + 7 = 48。

功能说明

在下面的编辑器中完成子字符串功能。 子字符串具有以下参数： 字符串 n：整数的字符串表示形式 退货

int：n中所有子串的整数值之和，模(10⁹+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)-1, -1,-1): 
        totalSum += substrSum(i) 
        
    return totalSum % (10 ** 9 + 7) 

我还尝试了带有记忆功能的递归自下而上动态编程解决方案（这仅涉及更改

for

循环计数方向）：

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) 

对于自上而下的解决方案，在 13 个测试用例中的 8 个中给出了运行时错误，而在自下而上的解决方案中，在 13 个测试用例中的 6 个中给出了运行时错误。我哪里出错了？

Answer 1

您的算法是正确的（两个版本），但 HackerRank 将使用具有数千位数字的字符串进行测试，并且当您对每个数字执行递归调用时，您的第一个代码会遇到“超出最大递归深度”错误，并且第二个遇到内存错误（想想缓存）。 应该指出的是，他们对“约束”的措辞是错误的。受 2 x 10

5

限制的不是n“转换为整数”的值，而是n中的^位数。我查了一下，他们的一个测试涉及一串大约 199000 位数字。

public class Main {

public static int sumOfSubstrings(String n) {
    final int MOD = 1000000007;
    int length = n.length();
    long totalSum = 0;
    long multiplier = 1;

    for (int i = length - 1; i >= 0; i--) {
        int digit = Character.getNumericValue(n.charAt(i));
        totalSum = (totalSum + digit * (i + 1) * multiplier) % MOD;
        multiplier = (multiplier * 10 + 1) % MOD;
    }

    return (int) totalSum;
}

Answer 2