如何解决这个动态规划问题？

Question

我在学习动态规划时遇到了一个问题。

给定一个数字字符串，需要找到该字符串的子串中，前半部分和后半部分数字之和相等的最长子串长度。

例如：

输入字符串：142124

输出 ：6

当输入字符串为"142124"时，前半部分(142)和后半部分(124)的数字之和相等，所以整个字符串就成为我们找到的最长子串。因此，输出为6，即整个字符串的长度。

输入字符串：9430723

输出：4

这个字符串中，前半部分和后半部分数字之和相等的最长子串为"4307"。

我是这样解决这个问题的：

int maxSubStringLength(char* str){ 
int n = strlen(str);
int maxLen = 0;

int sum[n][n];

for(int i=0; i<n; i++)
    sum[i][i] = str[i] - '0';

for(int len =2; len <=n; len++){
    for(int i = 0; i < n - len + 1; i++){
        int j = i + len - 1;
        int k = len / 2;
        sum[i][j] = sum[i][j-k] + sum[j-k+1][j];

        if(len%2 == 0 && sum[i][j-k] == sum[j-k+1][j] && len > maxLen)
            maxLen = len;
        }
    }
    return maxLen;
}

这段代码的时间复杂度为O(n*n)，空间复杂度为O(n*n)。

然而，这个问题需要用O(1)的空间复杂度和O(n * n)的时间复杂度来解决。

是否可能用O (1)的空间复杂度来解决这个问题？

- renatus

---

对我来说，“O(1)空间复杂度”和“动态规划”看起来互相排斥。你真的想在这个问题中使用动态规划吗？如果是，为什么？ - anatolyg

虽然有人发布了一个O(1)的解决方案，但要求在动态规划问题中使用这种限制有点奇怪，整个重点是利用先前的结果来形成更进一步的结果。 - Xgh05t

Answer 1

你可以使用O(1)的空间复杂度和O(n^2)的时间复杂度轻松解决这个问题。

以下是一种方法：

1. 从m=0到n-2进行循环。这表示字符串的中间部分（在第m个字符后拆分）。 2. 对于i = 1到n（如果越界则退出），构建左侧和右侧的求和，如果它们相等，则将i与目前为止最好的比较并进行更新。 3. 解决方案是2倍于最好的（因为它表示了一半的字符串）。

在Java中，它可能是这样的：

public int maxSubstringLength(String s) {
    int best = 0;
    for (int m = 0; m < s.length() - 1; m++) {
        int l = 0; // left sum
        int r = 0; // right sum
        for (int i = 1; m - i + 1 >= 0 && m + i < s.length(); i++) {
            l += s.charAt(m - i + 1);
            r += s.charAt(m + i);
            if (l == r && i > best)
                best = i;
        }
    }
    return 2 * best;
}

- maraca