这道题的核心是动态规划 前缀和优化。因为数组的增减趋势必须交替如 abcd我们只需记录最后一个值和最后一步方向。核心思路· 状态定义up[i] 表示最后一步为上升且以值 i 结尾的方案数down[i] 同理为下降。· 状态转移· 要形成新的上升到 x前一步必须是下降且结尾值 xnewUp[x] sum(down[0] ... down[x-1])。· 要形成新的下降到 x前一步必须是上升且结尾值 xnewDown[x] sum(up[x1] ... up[m-1])。· 优化用前缀和快速计算 newUp用后缀和快速计算 newDown避免遍历求和将复杂度从 O(n·m²) 降至 O(n·m)。---Java 实现空间优化版 O(m)javaclass Solution {private static final int MOD 1_000_000_007;public int zigZagArrays(int n, int l, int r) {int m r - l 1; // 取值个数// 初始化长度为 1 的情况每个值都可以作为起点long[] up new long[m];long[] down new long[m];for (int i 0; i m; i) {up[i] 1;down[i] 1;}// 重复 n-1 次每次在末尾添加一个数for (int len 2; len n; len) {long[] newUp new long[m];long[] newDown new long[m];// 计算前缀和用于 newUplong prefixSum 0;for (int x 0; x m; x) {newUp[x] prefixSum; // sum of down[0..x-1]prefixSum (prefixSum down[x]) % MOD;}// 计算后缀和用于 newDownlong suffixSum 0;for (int x m - 1; x 0; x--) {newDown[x] suffixSum; // sum of up[x1..m-1]suffixSum (suffixSum up[x]) % MOD;}up newUp;down newDown;}// 答案所有 up 和 down 之和long ans 0;for (int i 0; i m; i) {ans (ans up[i] down[i]) % MOD;}return (int) ans;}}另一种写法滚动数组 前缀和数组使用 prefixSums 和 suffixSums 辅助计算javaclass Solution {private static final int MOD 1_000_000_007;public int zigZagArrays(int n, int l, int r) {int m r - l 1;int[] up new int[m];int[] down new int[m];int[] prefixUp new int[m 1];int[] prefixDown new int[m 1];for (int j 0; j m; j) {up[j] 1;down[j] 1;prefixUp[j 1] (prefixUp[j] up[j]) % MOD;prefixDown[j 1] (prefixDown[j] down[j]) % MOD;}for (int i 1; i n; i) {int[] newUp new int[m];int[] newDown new int[m];int[] newPrefixUp new int[m 1];int[] newPrefixDown new int[m 1];for (int j 0; j m; j) {// 上升前一步下降且值 jnewUp[j] (j 0) ? prefixDown[j] : 0; // prefixDown[j] sum(down[0..j-1])// 下降前一步上升且值 jnewDown[j] (j 1 m) ? (prefixUp[m] - prefixUp[j 1] MOD) % MOD : 0;newPrefixUp[j 1] (newPrefixUp[j] newUp[j]) % MOD;newPrefixDown[j 1] (newPrefixDown[j] newDown[j]) % MOD;}up newUp;down newDown;prefixUp newPrefixUp;prefixDown newPrefixDown;}return (prefixUp[m] prefixDown[m]) % MOD;}}复杂度· 时间复杂度O(n·m)· 空间复杂度O(m)
