找到所有可能的数组，给定一个缺少元素的数组，使得所有连续元素的绝对差 >= 1 [关闭]

Question

一个学生被要求为数组 arr 中表示的同学分配数字。如果任意两个连续同学的绝对差小于等于1，则数字的排列是好的。例如数组

[1, 2, 1]

是好的，而

[2, 1, 3]

则不是，因为abs(1 - 3) = 2，大于 1.

n 个整数的数组 arr 有一些缺失的元素，用

arr[i] = 0

表示。找到用任意整数替换部分或全部缺失元素的方法的数量，以便生成的数组是好的。由于答案可能很大，计算它模 (1^9 + 7)。

例子

考虑 n = 3, arr = [0, 0, 1].

有 9 种方法可以替换 0 来使数组变好。

arr = [0, 0, 1]
arr = [1, 0, 1]
arr = [-1, 0, 1]
arr = [0, 1, 1]
arr = [1, 1, 1]
arr = [2, 1, 1]
arr = [1, 2, 1]
arr = [2, 2, 1]
arr = [3, 2, 1]

在这些数组的每一个中，每对连续元素之间的绝对差值小于或等于1。

功能说明

函数返回一个整数，表示替换缺失元素以形成良好数组的方法数，取模（1^9 + 7）。

countGoodArrays 具有以下参数：

int arr[n]: an array of integers

约束

1 ≤ n ≤ 1500
0 ≤ arr[i] ≤ 10^9
There is at least one element in arr which is not equal to 0.

示例测试用例

arr = [1, 0, 0, 2] ans = 6

arr = [0, 1, 1, 0] ans = 9

好像是DP题，挺难的。我无法想出一个解决方案，但这就是我得到的，它通过了我提到的两个测试用例，但其他所有测试都失败了。

例如 [0, 0, 5, 4, 0, 3, 3] 输出 16 这是错误的，我认为正确答案是 7.

def countGoodArrays(arr):
MOD = 10**9 + 7
n = len(arr)
dp = [[0] * (n+1) for _ in range(n)]
for j in range(n):
    if arr[0] == 0 or arr[0] == j:
        dp[0][j] = 1
for i in range(1, n):
    for j in range(n):
        if arr[i] == 0 or arr[i] == j:
            for k in range(n):
                if abs(j-k) <= 1:
                    dp[i][j] += dp[i-1][k]
                    dp[i][j] %= MOD
ans = 0
for j in range(n):
    if arr[n-1] == 0 or arr[n-1] == j:
        ans += dp[n-1][j]
        ans %= MOD
return ans