周赛三四题的水准，两道题目只在数据规模上有差异，目前只能尝试写灵神题解的解释。
这题虽然对两个数组有要求，但是实际上只需要枚举其中一个数组的情况，把对另外一个数组中元素的要求当成约束就行。
根据动态规划缩小问题规模的思想：
- 原问题是下标 0 0 0 到 n − 1 n - 1 n−1中的单调数组对的个数，且 a r r 1 [ n − 1 ] = j = 0 , 1 , 2 , . . . , n u m s [ n − 1 ] arr_1[n−1] = j = 0, 1, 2, ..., nums[n - 1] arr1[n−1]=j=0,1,2,...,nums[n−1]。
- 子问题是下标 0 0 0 到 i i i 中的单调数组对的个数，且 a r r 1 [ i ] = j arr_1[i] = j arr1[i]=j，将其记作 d p [ i ] [ j ] dp[i][j] dp[i][j]。
用
k
k
k表示
a
r
r
1
[
i
−
1
]
arr_1[i−1]
arr1[i−1]，那么根据约束条件：
{
a
r
r
1
[
i
−
1
]
≤
a
r
r
1
[
i
]
a
r
r
2
[
i
−
1
]
≥
a
r
r
2
[
i
]
\ \begin{cases} arr_1[i - 1] \le arr_1[i] \\ arr_2[i - 1] \ge arr_2[i] \\ \end{cases}
{arr1[i−1]≤arr1[i]arr2[i−1]≥arr2[i]，即
{
k
≤
j
n
u
m
s
[
i
−
1
]
−
k
≥
n
u
m
s
[
i
]
−
j
\ \begin{cases} k \le j \\ nums[i - 1] - k \ge nums[i] - j \\ \end{cases}
{k≤jnums[i−1]−k≥nums[i]−j，可以得到
k
k
k 的上界。
解得
k
≤
m
i
n
(
j
,
n
u
m
s
[
i
−
1
]
−
n
u
m
s
[
i
]
+
j
)
=
j
+
m
i
n
(
n
u
m
s
[
i
−
1
]
−
n
u
m
s
[
i
]
,
0
)
k \le min(j, nums[i - 1] - nums[i] + j) = j + min(nums[i - 1] - nums[i], 0)
k≤min(j,nums[i−1]−nums[i]+j)=j+min(nums[i−1]−nums[i],0)，由于所有数组中的元素都是非负的，而
n
u
m
s
[
i
]
=
a
r
r
1
[
i
]
+
a
r
r
2
[
i
]
nums[i] = arr_1[i] + arr_2[i]
nums[i]=arr1[i]+arr2[i]，所以
k
≤
n
u
m
s
[
i
−
1
]
k \le nums[i - 1]
k≤nums[i−1]。
记
m
a
x
K
=
j
+
m
i
n
(
n
u
m
s
[
i
−
1
]
−
n
u
m
s
[
i
]
,
0
)
maxK = j + min(nums[i - 1] - nums[i], 0)
maxK=j+min(nums[i−1]−nums[i],0)，那么
d
p
[
i
]
[
j
]
=
{
0
，
m
a
x
K
<
0
Σ
k
=
0
m
a
x
K
d
p
[
i
−
1
]
[
k
]
，
m
a
x
K
≥
0
dp[i][j] = \begin{cases} 0，& maxK \lt 0 \\ \mathop{\Sigma} \limits _ {k = 0} ^ {maxK} dp[i - 1][k]，& maxK \ge 0 \\ \end{cases}
dp[i][j]=⎩
⎨
⎧0，k=0ΣmaxKdp[i−1][k]，maxK<0maxK≥0。
这里
Σ
k
=
0
m
a
x
K
d
p
[
i
−
1
]
[
k
]
\mathop{\Sigma} \limits _ {k = 0} ^ {maxK} dp[i - 1][k]
k=0ΣmaxKdp[i−1][k] 表示对所有的
k
k
k 从
0
0
0 到
m
a
x
K
maxK
maxK 的情况，求下标
0
0
0 到
i
−
1
i - 1
i−1 中的单调数组对的个数之和，要求
a
r
r
1
=
k
arr_1 = k
arr1=k。这显然满足前缀和的定义，记
s
[
j
]
=
Σ
k
=
0
j
d
p
[
i
−
1
]
[
k
]
s[j] = \mathop{\Sigma} \limits _ {k = 0} ^ {j} dp[i - 1][k]
s[j]=k=0Σjdp[i−1][k]，那么上述状态转移方程
(
3
)
(3)
(3) 可以简化为
d
p
[
i
]
[
j
]
=
{
0
，
m
a
x
K
<
0
s
[
m
a
x
K
]
，
m
a
x
K
≥
0
dp[i][j] = \begin{cases} 0，& maxK \lt 0 \\ s[maxK]，& maxK \ge 0 \\ \end{cases}
dp[i][j]={0，s[maxK]，maxK<0maxK≥0。
初始值
d
p
[
0
]
[
j
]
=
1
dp[0][j] = 1
dp[0][j]=1，其中
j
=
0
,
1
,
2
,
.
.
.
,
n
u
m
s
[
0
]
j = 0, 1, 2, ..., nums[0]
j=0,1,2,...,nums[0]。这表示的是，下标
0
0
0 到
0
0
0 中的单调数组对的个数，也就是只考虑数组中第一个元素的情况，
a
r
r
1
[
i
]
arr_1[i]
arr1[i] 可以是合法范围内任意值。
后续还有进一步优化，目前一下子掌握不了，先暂时放弃。