基于已收集的信息我为你提供 LeetCode 3883. 统计满足数位和数组的非递减数组数目 的 Java 实现。题目分析- 给定 digitSum 数组要求构造非递减数组 arr其中 0 arr[i] 5000 且 arr[i] 的数位和等于 digitSum[i]- 由于 arr[i] 的上界是 5000且 digitSum[i] 50我们可以预处理每个数位和对应的所有合法数字- 使用 DP 前缀和优化f[i][j] 表示前 i 个元素中第 i 个元素恰好为 j 的有效数组数量。由于数组非递减f[i][j] 可以从所有 f[i-1][j j] 转移过来用前缀和优化到 O(5000) 每层Java 实现javaclass Solution {private static final int MOD 1_000_000_007;private static final int MAX_VAL 5000;// 预处理digitSumToNumbers[s] 表示数位和为 s 的所有数字0 num 5000private static final ListInteger[] digitSumToNumbers new List[51];static {for (int s 0; s 50; s) {digitSumToNumbers[s] new ArrayList();}for (int num 0; num MAX_VAL; num) {digitSumToNumbers[digitSum(num)].add(num);}}private static int digitSum(int x) {int s 0;while (x 0) {s x % 10;x / 10;}return s;}public int countArrays(int[] digitSum) {int n digitSum.length;// dp[j] 表示当前位置以数字 j 结尾的有效数组数量long[] dp new long[MAX_VAL 1];long[] prefix new long[MAX_VAL 1];// 初始化第一个位置int firstSum digitSum[0];if (digitSumToNumbers[firstSum].isEmpty()) {return 0;}for (int num : digitSumToNumbers[firstSum]) {dp[num] 1;}// 计算前缀和prefix[0] dp[0];for (int i 1; i MAX_VAL; i) {prefix[i] (prefix[i - 1] dp[i]) % MOD;}// 处理后续位置for (int idx 1; idx n; idx) {int s digitSum[idx];ListInteger validNumbers digitSumToNumbers[s];if (validNumbers.isEmpty()) {return 0;}long[] newDp new long[MAX_VAL 1];// 对于每个合法的 numnewDp[num] prefix[num]即所有 num 的 dp 之和for (int num : validNumbers) {newDp[num] prefix[num];}dp newDp;// 重新计算前缀和prefix[0] dp[0];for (int i 1; i MAX_VAL; i) {prefix[i] (prefix[i - 1] dp[i]) % MOD;}}return (int) (prefix[MAX_VAL] % MOD);}}复杂度分析- 时间复杂度O(n × MAX_VAL)其中 n digitSum.length 1000MAX_VAL 5000。预处理是常数时间每轮 DP 需要遍历所有合法数字并重新计算前缀和。- 空间复杂度O(MAX_VAL)使用滚动数组优化只保留一维 DP 状态。关键优化点1. 预处理合法数字由于值域固定 [0, 5000]预先按数位和分组避免每轮重复计算2. 前缀和优化转移非递减约束要求 arr[i-1] arr[i]通过前缀和将 O(MAX_VAL²) 的转移优化到 O(MAX_VAL)3. 滚动数组只保留上一层的 dp 数组空间从 O(n × MAX_VAL) 降到 O(MAX_VAL)