标签： 动态规划

目标

给你一个由 正 整数组成的数组 nums，以及一个 正 整数 k。

你可以对 nums 执行 一次 操作，该操作中可以移除任意 不重叠 的前缀和后缀，使得 nums 仍然 非空 。

你需要找出 nums 的 x 值，即在执行操作后，剩余元素的 乘积 除以 k 后的 余数 为 x 的操作数量。

返回一个大小为 k 的数组 result，其中 result[x] 表示对于 0 <= x <= k - 1，nums 的 x 值。

数组的 前缀 指从数组起始位置开始到数组中任意位置的一段连续子数组。

数组的 后缀 是指从数组中任意位置开始到数组末尾的一段连续子数组。

子数组 是数组中一段连续的元素序列。

注意，在操作中选择的前缀和后缀可以是 空的 。

示例 1：

输入： nums = [1,2,3,4,5], k = 3
输出： [9,2,4]
解释：
对于 x = 0，可行的操作包括所有不会移除 nums[2] == 3 的前后缀移除方式。
对于 x = 1，可行操作包括：
    移除空前缀和后缀 [2, 3, 4, 5]，nums 变为 [1]。
    移除前缀 [1, 2, 3] 和后缀 [5]，nums 变为 [4]。
对于 x = 2，可行操作包括：
    移除空前缀和后缀 [3, 4, 5]，nums 变为 [1, 2]。
    移除前缀 [1] 和后缀 [3, 4, 5]，nums 变为 [2]。
    移除前缀 [1, 2, 3] 和空后缀，nums 变为 [4, 5]。
    移除前缀 [1, 2, 3, 4] 和空后缀，nums 变为 [5]。

示例 2：

输入： nums = [1,2,4,8,16,32], k = 4
输出： [18,1,2,0]
解释：
对于 x = 0，唯一 不 得到 x = 0 的操作有：
    移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
    移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 1，唯一的操作是：
    移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
对于 x = 2，可行操作包括：
    移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
对于 x = 3，没有可行的操作。

示例 3：

输入： nums = [1,1,2,1,1], k = 2
输出： [9,6]

说明：

• 1 <= nums[i] <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= k <= 5

思路

有一个正整数数组 nums 和一个正整数 k，每次操作可以移除数组不重叠的前缀与后缀，即保留中间非空的子数组。求子数组元素乘积模 k 的余数为 x 的操作数量。

定义 dp[i][j] 表示 [0, i] 中以 i 为右端点的子数组中模 k 余 j 的个数。使用刷表法更新 dp[i][nums[i] % k]++, dp[i][nums[i] * j % k] += dp[i - 1][j]。

代码

/**
 * @date 2026-09-21 15:19
 */
public class ResultArray3524 {

    public long[] resultArray(int[] nums, int k) {
        int n = nums.length;
        long[][] dp = new long[n][k];
        dp[0][nums[0] % k] = 1;
        long[] res = new long[k];
        res[nums[0] % k]++;
        for (int i = 1; i < n; i++) {
            int rem = nums[i] % k;
            dp[i][rem]++;
            for (int j = 0; j < k; j++) {
                dp[i][(int) ((long) nums[i] * j % k)] += dp[i - 1][j];
            }
            for (int j = 0; j < k; j++) {
                res[j] += dp[i][j];
            }
        }
        return res;
    }

}

性能

目标

给你一个整数数组 arr 和一个整数值 target 。

请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。

请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。

示例 1：

输入：arr = [3,2,2,4,3], target = 3
输出：2
解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。

示例 2：

输入：arr = [7,3,4,7], target = 7
输出：2
解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。

示例 3：

输入：arr = [4,3,2,6,2,3,4], target = 6
输出：-1
解释：我们只有一个和为 6 的子数组。

示例 4：

输入：arr = [5,5,4,4,5], target = 3
输出：-1
解释：我们无法找到和为 3 的子数组。

示例 5：

输入：arr = [3,1,1,1,5,1,2,1], target = 3
输出：3
解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。

说明：

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 1000
• 1 <= target <= 10^8

思路

有一个整数数组 arr 和一个整数值 target，从数组中找到两个不重叠的子数组，使得子数组的和为 target，返回这两个子数组长度之和的最小值。

将重叠问题进行前后缀分解，在各自的部分只需考虑和为 target 的最小长度，最小长度可以使用滑动窗口。

代码

/**
 * @date 2026-09-17 10:06
 */
public class MinSumOfLengths1477 {

    public int minSumOfLengths(int[] arr, int target) {
        int n = arr.length;
        int[] pre = new int[n + 1];
        int[] suf = new int[n + 1];
        Arrays.fill(pre, Integer.MAX_VALUE);
        Arrays.fill(suf, Integer.MAX_VALUE);
        int sum = 0;
        int l = 0;
        for (int i = 0; i < n; i++) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[l++];
            }
            if (sum == target) {
                pre[i + 1] = Math.min(pre[i], i - l + 1);
            } else {
                pre[i + 1] = pre[i];
            }
        }
        sum = 0;
        int r = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
            while (sum > target) {
                sum -= arr[r--];
            }
            if (sum == target) {
                suf[i] = Math.min(suf[i + 1], r - i + 1);
            } else {
                suf[i] = suf[i + 1];
            }
        }
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (pre[i + 1] != Integer.MAX_VALUE && suf[i + 1] != Integer.MAX_VALUE) {
                res = Math.min(res, pre[i + 1] + suf[i + 1]);
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

性能

目标

给你一维空间的 n 个点，其中第 i 个点（编号从 0 到 n-1）位于 x = i 处，请你找到 恰好 k 个不重叠 线段且每个线段至少覆盖两个点的方案数。线段的两个端点必须都是 整数坐标 。这 k 个线段不需要全部覆盖全部 n 个点，且它们的端点 可以 重合。

请你返回 k 个不重叠线段的方案数。由于答案可能很大，请将结果对 10^9 + 7 取余 后返回。

示例 1：

输入：n = 4, k = 2
输出：5
解释：
如图所示，两个线段分别用红色和蓝色标出。
上图展示了 5 种不同的方案 {(0,2),(2,3)}，{(0,1),(1,3)}，{(0,1),(2,3)}，{(1,2),(2,3)}，{(0,1),(1,2)} 。

示例 2：

输入：n = 3, k = 1
输出：3
解释：总共有 3 种不同的方案 {(0,1)}, {(0,2)}, {(1,2)} 。

示例 3：

输入：n = 30, k = 7
输出：796297179
解释：画 7 条线段的总方案数为 3796297200 种。将这个数对 10^9 + 7 取余得到 796297179 。

示例 4：

输入：n = 5, k = 3
输出：7

示例 5：

输入：n = 3, k = 2
输出：1

说明：

• 2 <= n <= 1000
• 1 <= k <= n-1

思路

数轴上有 n 个点，编号为 0 ~ n - 1，求从中选择 k 个不重叠线段（至少覆盖两个点）的方案数。线段 [a, b] 与 [c, d] 不重叠指 b <=c 或 d <= a。

定义 dp[i][k] 表示 [0, i] 中恰好 k 个不重叠线段的方案数。根据选或者不选 i 考虑状态转移方程，如果不选 i，方案数等于前面的方案数，如果选，需要枚举前面所有的 p ∈ [0, i - 1]，累加 dp[p][j - 1]。

• dp[i][j] = (dp[i - 1][j] + sum) % mod，sum = Σdp[p][j - 1], p ∈ [0, i - 1]

代码

/**
 * @date 2026-09-17 15:31
 */
public class NumberOfSets1621 {

    public int numberOfSets(int n, int k) {
        int mod = 1000000007;
        int[][] dp = new int[n][k + 1];
        dp[0][0] = 1;
        int[] prefix = new int[k + 1];
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                prefix[j] = (prefix[j] + dp[i - 1][j - 1]) % mod;
                dp[i][j] = (dp[i - 1][j] + prefix[j]) % mod;
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            res = (res + dp[i][k]) % mod;
        }
        return res;
    }

}

性能

目标

Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。

游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。

Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。

假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。

示例 1：

输入：piles = [5,3,4,5]
输出：true
解释：
Alice 先开始，只能拿前 5 颗或后 5 颗石子 。
假设他取了前 5 颗，这一行就变成了 [3,4,5] 。
如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。
如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。
这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。

示例 2：

输入：piles = [3,7,2,3]
输出：true

说明：

• 2 <= piles.length <= 500
• piles.length 是 偶数
• 1 <= piles[i] <= 500
• sum(piles[i]) 是 奇数

思路

有偶数堆石子排成一行，piles[i] 表示第 i 堆石子的数量，石子总数为奇数。从 Alice 开始，与 Bob 轮流取走左侧或右侧的整堆石子，直到取走所有石子堆为止。获得石子最多的玩家获胜。假设 Alice 与 Bob 都能做出最优的选择，判断 Alice 能否获胜。

定义 dp[i][j] 表示剩余石堆为 [i, j] 时，先手与后手获得的石子数量之差的最大值。dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])。

• 先手 A 选择 i，剩余问题变成 B 先手 [i + 1, j]，而当前问题的先手是 A，剩余问题则是 B - A，应该取相反数。
• 先手 A 选择 j 同理。

外层倒序遍历，内存正序遍历。因为 i 依赖 i + 1，j 依赖 j - 1。初始化 dp[i][i] = pilesp[i]。

本题使用了空间优化，当前状态是从下方与左侧转移而来，从右下角到左上对角线开始，从左向右更新。每次状态更新只用到了下方与左侧的值，因此可以使用滚动数组保存下方的值。

先手玩家必定可以获胜，首先石子总数为奇数（不可能平局），奇数堆与偶数堆的石子数量必定不同，先手可以控制自己只选择偶数堆或者奇数堆，因此必胜。

因为开始时首尾的奇偶性不同，偶，……，奇，如果奇数堆的石子更多，那么先手就选奇数堆，这时留给后手的只有首尾的两个偶数下标。

代码

/**
 * @date 2026-08-03 14:45
 */
public class StoneGame877 {

    public boolean stoneGame_v1(int[] piles) {
        return true;
    }

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[] dp = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            dp[i] = piles[i];
            for (int j = i + 1; j < n; j++) {
                dp[j] = Math.max(piles[i] - dp[j], piles[j] - dp[j - 1]);
            }
        }
        return dp[n - 1] > 0;
    }
}

性能