python - DP求解0和1个数相等的连续子数组的最大长度

Question

问题出自这里https://leetcode.com/problems/contiguous-array/

其实这道题我想出了一个DP解法。 但是，它不会通过一个测试用例。

有什么想法吗？

DP[i][j] ==1 表示从子串[i]到子串[j]有效

将问题分成更小的部分

DP[i][j]==1

- if DP[i+2][j]==1 and DP[i][i+1]==1
- else if DP[i][j-2]==1 and DP[j-1][j]==1
- else if num[i],num[j] == set([0,1]) and DP[i+1][j-1]==1

``` current_max_len = 0 如果不是数字: 返回 current_max_len

    dp = [] * len(nums)
    for _ in range(len(nums)):
        dp.append([None] * len(nums))

    for thisLen in range(2, len(nums)+1, 2):
        for i in range(len(nums)):
            last_index = i + thisLen -1
            if i + thisLen > len(nums):
                continue

            if thisLen==2:
                if set(nums[i:i+2]) == set([0, 1]):
                    dp[i][last_index] = 1
            elif dp[i][last_index-2] and dp[last_index-1][last_index]:
                dp[i][last_index] = 1
            elif dp[i][i + 1] and dp[i + 2][last_index]:
                dp[i][last_index] = 1
            elif dp[i + 1][last_index-1] and set([nums[i], nums[last_index]]) == set([0, 1]):
                dp[i][last_index] = 1
            else:
                dp[i][last_index] = 0
            if dp[i][last_index] == 1:
                current_max_len = max(current_max_len, thisLen)

    return current_max_len

```

Answer 1

这是一个反例[1, 1, 0, 0, 0, 0, 1, 1]。您解决方案的问题是，在这个反例中，它需要一个列表由大小为 n-1 或 n-2 的较小有效列表组成，它是两个长度为 4 或 n-2 的列表 。 -- 剧透警告 -- 你可以通过使用其他 dp 技术来解决这个问题列出每个索引 i