Hard
题目描述
给定三个整数 n、l 和 r。
长度为 n 的 Z字形数组定义如下：
- 每个元素都在范围 [l, r] 内。
- 没有两个相邻元素相等。
- 没有三个连续元素形成严格递增或严格递减序列。
返回有效 Z字形数组的总数。
由于答案可能很大，请返回对 10^9 + 7 取模的结果。
如果序列中每个元素都严格大于前一个元素（如果存在），则称该序列严格递增。
如果序列中每个元素都严格小于前一个元素（如果存在），则称该序列严格递减。
示例 1：
输入：n = 3, l = 4, r = 5
输出：2
解释：
只有 2 个有效的长度为 n = 3、使用范围 [4, 5] 中值的 Z字形数组：
[4, 5, 4]
[5, 4, 5]
示例 2：
输入：n = 3, l = 1, r = 3
输出：10
解释：
有 10 个有效的长度为 n = 3、使用范围 [1, 3] 中值的 Z字形数组：
[1, 2, 1], [1, 3, 1], [1, 3, 2]
[2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
[3, 1, 2], [3, 1, 3], [3, 2, 3]
所有数组都满足 Z字形条件。
约束：
- 3 <= n <= 2000
- 1 <= l < r <= 2000
解题思路
这是一个典型的动态规划问题。我们需要追踪数组构建过程中的状态变化。
核心思路：
- 使用三维DP：
dp[i][dir][x]表示长度为 i、以值 x 结尾、下一步需要向 dir 方向变化的数组数量 dir = 0表示下一个元素需要比当前元素小（向下）dir = 1表示下一个元素需要比当前元素大（向上）
状态转移：
- 如果当前需要向上（dir=1），那么下一个值 y 必须大于当前值 x，且下一步需要向下
- 如果当前需要向下（dir=0），那么下一个值 y 必须小于当前值 x，且下一步需要向上
优化技巧： 为了避免 O(m²) 的复杂度，我们使用前缀和来优化状态转移：
- 维护前缀和数组，快速计算满足条件的状态总和
- 每层更新的复杂度从 O(m²) 降低到 O(m)
初始化： 前两个位置可以任意选择（只要不相等），从第三个位置开始应用Z字形约束。
代码实现
class Solution {
public:
int zigZagArrays(int n, int l, int r) {
const int MOD = 1e9 + 7;
int m = r - l + 1;
// dp[dir][x] = count of sequences ending at value x with next direction dir
vector<vector<long long>> dp(2, vector<long long>(m, 0));
vector<vector<long long>> newDp(2, vector<long long>(m, 0));
// Initialize first two positions
// First position: any value
for (int x = 0; x < m; x++) {
for (int y = 0; y < m; y++) {
if (x != y) {
if (x < y) {
dp[0][y]++; // next should go down
} else {
dp[1][y]++; // next should go up
}
}
}
}
// Build remaining positions
for (int i = 2; i < n; i++) {
fill(newDp[0].begin(), newDp[0].end(), 0);
fill(newDp[1].begin(), newDp[1].end(), 0);
// Prefix sums for optimization
vector<long long> prefixUp(m + 1, 0), prefixDown(m + 1, 0);
for (int x = 0; x < m; x++) {
prefixUp[x + 1] = (prefixUp[x] + dp[1][x]) % MOD;
prefixDown[x + 1] = (prefixDown[x] + dp[0][x]) % MOD;
}
for (int y = 0; y < m; y++) {
// If next direction should be up (dir=1), current came from down trend
// So previous values should be > y
if (y + 1 < m) {
newDp[1][y] = (prefixDown[m] - prefixDown[y + 1] + MOD) % MOD;
}
// If next direction should be down (dir=0), current came from up trend
// So previous values should be < y
if (y > 0) {
newDp[0][y] = prefixUp[y] % MOD;
}
}
dp = newDp;
}
long long result = 0;
for (int x = 0; x < m; x++) {
result = (result + dp[0][x] + dp[1][x]) % MOD;
}
return result;
}
};
class Solution:
def zigZagArrays(self, n: int, l: int, r: int) -> int:
MOD = 10**9 + 7
m = r - l + 1
# dp[dir][x] = count of sequences ending at value x with next direction dir
dp = [[0] * m for _ in range(2)]
# Initialize first two positions
for x in range(m):
for y in range(m):
if x != y:
if x < y:
dp[0][y] += 1 # next should go down
else:
dp[1][y] += 1 # next should go up
# Build remaining positions
for i in range(2, n):
new_dp = [[0] * m for _ in range(2)]
# Prefix sums for optimization
prefix_up = [0] * (m + 1)
prefix_down = [0] * (m + 1)
for x in range(m):
prefix_up[x + 1] = (prefix_up[x] + dp[1][x]) % MOD
prefix_down[x + 1] = (prefix_down[x] + dp[0][x]) % MOD
for y in range(m):
# If next direction should be up (dir=1), current came from down trend
if y + 1 < m:
new_dp[1][y] = (prefix_down[m] - prefix_down[y + 1]) % MOD
# If next direction should be down (dir=0), current came from up trend
if y > 0:
new_dp[0][y] = prefix_up[y] % MOD
dp = new_dp
return sum(dp[0][x] + dp[1][x] for x in range(m)) % MOD
public class Solution {
public int ZigZagArrays(int n, int l, int r) {
const int MOD = 1000000007;
int m = r - l + 1;
// dp[dir][x] = count of sequences ending at value x with next direction dir
long[,] dp = new long[2, m];
long[,] newDp = new long[2, m];
// Initialize first two positions
for (int x = 0; x < m; x++) {
for (int y = 0; y < m; y++) {
if (x != y) {
if (x < y) {
dp[0, y]++; // next should go down
} else {
dp[1, y]++; // next should go up
}
}
}
}
// Build remaining positions
for (int i = 2; i < n; i++) {
Array.Clear(newDp, 0, newDp.Length);
// Prefix sums for optimization
long[] prefixUp = new long[m + 1];
long[] prefixDown = new long[m + 1];
for (int x = 0; x < m; x++) {
prefixUp[x + 1] = (prefixUp[x] + dp[1, x]) % MOD;
prefixDown[x + 1] = (prefixDown[x] + dp[0, x]) % MOD;
}
for (int y = 0; y < m; y++) {
// If next direction should be up (dir=1), current came from down trend
if (y + 1 < m) {
newDp[1, y] = (prefixDown[m] - prefixDown[y + 1] + MOD) % MOD;
}
// If next direction should be down (dir=0), current came from up trend
if (y > 0) {
newDp[0, y] = prefixUp[y] % MOD;
}
}
Array.Copy(newDp, dp, newDp.Length);
}
long result = 0;
for (int x = 0; x < m; x++) {
result = (result + dp[0, x] + dp[1, x]) % MOD;
}
return (int)result;
}
}
var zigZagArrays = function(n, l, r) {
const MOD = 1e9 + 7;
const m = r - l + 1;
// dp[dir][x] = count of sequences ending at value x with next direction dir
let dp = Array(2).fill().map(() => Array(m).fill(0));
// Initialize first two positions
for (let x = 0; x < m; x++) {
for (let y = 0; y < m; y++) {
if (x !== y) {
if (x < y) {
dp[0][y]++; // next should go down
} else {
dp[1][y]++; // next should go up
}
}
}
}
// Build remaining positions
for (let i = 2; i < n; i++) {
const newDp = Array(2).fill().map(() => Array(m).fill(0));
// Prefix sums for optimization
const prefixUp = Array(m + 1).fill(0);
const prefixDown = Array(m + 1).fill(0);
for (let x = 0; x < m; x++) {
prefixUp[x + 1] = (prefixUp[x] + dp[1][x]) % MOD;
prefixDown[x + 1] = (prefixDown[x] + dp[0][x]) % MOD;
}
for (let y = 0; y < m; y++) {
// If next direction should be up (dir=1), current came from down trend
if (y + 1 < m) {
newDp[1][y] = (prefixDown[m] - prefixDown[y + 1] + MOD) % MOD;
}
// If next direction should be down (dir=0), current came from up trend
if (y > 0) {
newDp[0][y] = prefixUp[y] % MOD;
}
}
dp = newDp;
}
let result = 0;
for (let x = 0; x < m; x++) {
result = (result + dp[0][x] + dp[1][x]) % MOD;
}
return result;
};
复杂度分析
| 复杂度 | 数值 |
|---|---|
| 时间复杂度 | O(n × m) |
| 空间复杂度 | O(m) |
其中 n 是数组长度，m = r - l + 1 是值域范围。通过前缀和优化，避免了朴素DP的 O(n × m²) 时间复杂度。