java - 我可以使用动态规划来降低时间复杂度吗？

Question

我有一个字符串数组，其中一个字符串是，

String s = "66678889966";

我需要将其输出为 60078009060

即；我将连续重复的字符设置为零，保留起始字符。

不仅是那个字符串，还有所有其他字符串，所以我无法避免外部循环来迭代所有这些字符串。

我用一种幼稚的方法解决了这个问题。实际上，我正在解决一个问题，其中包括另一个带有这样的字符串数组的循环。包括我的内部循环，它会上升到 O(n^2)，这是 Not Acceptable 。

BufferedReader bf = new BufferedReader(newInputStreamReader(System.in));
String s[], s1[];
s = bf.readLine().trim().split("\\s+");
s1 = bf.readLine().trim().split("\\s+");
BigInteger sb = new BigInteger(s[1]);
BigInteger sb1 = new BigInteger(s1[1]);
BigInteger indexIncre = new BigInteger("1");
BigInteger first = new BigInteger(s[1]);
BigInteger last = new BigInteger(s1[1]);
BigInteger length = last.subtract(first);
BigInteger summation = new BigInteger("0");
for (index = new BigInteger("0"); 
        !index.subtract(length).toString().equals("1"); 
        index =index.add(indexIncre)) {
    StringBuilder str = new StringBuilder(first.toString());
    int len = str.length();
    char c = str.charAt(0);
    for (int i = 1; i < len; i++) {
        if (str.charAt(i) == c) {
            str.setCharAt(i, '0');
        } else
            c = str.charAt(i);
    }
    first = first.add(indexIncre);
    summation = summation.add(new BigInteger(str.toString()));
}
BigInteger modulo = BigInteger.valueOf((long) Math.pow(10, 9) + 7);
System.out.println(summation.mod(modulo));

例如 输入

1 8
2 12

输出

49

其形式为

输入
NL L
NR R

NL、L、NR、R的取值范围为

1≤NL,NR≤10^5
1≤L≤R<10^100,000

修改值为f(x)

f(8)=8,f(9)=9,f(10)=10,f(11)=10,f(12)=12

并对所有这些 f(x) 之和取模 10^9+7

NL是最左边字符串的长度，L是字符串，NR是最右边字符串的长度，R是最右边字符串。例如问题中数字串8的长度为1，数字串12的长度为2，字符串总数为8,9,10,11,12

Answer 1

您总共有 'n' 个字符串。我们假设它们的平均长度为“m”。

您必须至少触摸每个字符串的每个字符一次，才能知道是否必须将该特定字符清零。因此，您可以实现的最佳复杂度是 O(m * n)，它是二次的。

O(m * n) 与通过嵌套循环方法迭代获得的复杂度相同。因此，您无法比采用动态编程/记忆化做得更好。