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

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)，space 复杂度为 O(n * n)。

但是，这个问题需要用O来解决（1）space复杂度用O（ n * n) 时间复杂度.

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

Answer 1

你可以轻松解决这个问题，复杂度为 O(1) space，时间复杂度为 O(n^2)。

这是一种方法：

从 m = 0 到 n-2。这表示字符串的中间（您在第 m 个字符之后拆分）。
For i = 1 to n (出界则断)。构建左右总和，如果它们相等，将 i 与目前最好的进行比较，如果更好则更新它。
解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;
}

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

How can I solve this dynamic programing problem?

algorithm

time-complexity

dynamic-programming

space-complexity