标签： 动态规划

2787.将一个数字表示成幂的和的方案数

目标

给你两个 正 整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1^x + n2^x + ... + nk^x 。

由于答案可能非常大，请你将它对 10^9 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 2^3 + 3^3 + 5^3 。

示例 1：

输入：n = 10, x = 2
输出：1
解释：我们可以将 n 表示为：n = 3^2 + 1^2 = 10 。
这是唯一将 10 表达成不同整数 2 次方之和的方案。

示例 2：

输入：n = 4, x = 1
输出：2
解释：我们可以将 n 按以下方案表示：
- n = 4^1 = 4 。
- n = 3^1 + 1^1 = 4 。

说明：

  • 1 <= n <= 300
  • 1 <= x <= 5

思路

求正整数的 x 次幂之和为 n 的组合数，要求组合中的数字不能重复。

最大正整数 max = n^(1/x)，问题转换为使用 1^x, 2^x, ……, max^x 组成 n 的组合数。

恰好型 0-1 背包。

代码


/**
 * @date 2025-08-12 9:08
 */
public class NumberOfWays2787 {

    public int numberOfWays(int n, int x) {
        int mod = 1000000007;
        int max = (int) Math.ceil(Math.pow(n, 1.0 / x));
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= max; i++) {
            int pow = (int) Math.pow(i, x);
            for (int j = n; j >= pow; j--) {
                dp[j] += dp[j - pow];
            }
        }
        return (int)(dp[n] % mod);
    }

}

性能

808.分汤

目标

你有两种汤，A 和 B，每种初始为 n 毫升。在每一轮中，会随机选择以下四种服务操作中的一种，每种操作的概率为 0.25，且与之前的所有轮次 无关：

  1. 从汤 A 取 100 毫升，从汤 B 取 0 毫升
  2. 从汤 A 取 75 毫升，从汤 B 取 25 毫升
  3. 从汤 A 取 50 毫升，从汤 B 取 50 毫升
  4. 从汤 A 取 25 毫升，从汤 B 取 75 毫升

注意：

  • 不存在先分配 100 ml 汤B 的操作。
  • 汤 A 和 B 在每次操作中同时被倒入。
  • 如果一次操作要求你倒出比剩余的汤更多的量，请倒出该汤剩余的所有部分。

操作过程在任何回合中任一汤被用完后立即停止。

返回汤 A 在 B 前耗尽的概率，加上两种汤在 同一回合 耗尽概率的一半。返回值在正确答案 10^-5 的范围内将被认为是正确的。

示例 1:

输入：n = 50
输出：0.62500
解释：
如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

示例 2:

输入：n = 100
输出：0.71875
解释：
如果我们选择第一个操作，A 首先将变为空。
如果我们选择第二个操作，A 将在执行操作 [1, 2, 3] 时变为空，然后 A 和 B 在执行操作 4 时同时变空。
如果我们选择第三个操作，A 将在执行操作 [1, 2] 时变为空，然后 A 和 B 在执行操作 3 时同时变空。
如果我们选择第四个操作，A 将在执行操作 1 时变为空，然后 A 和 B 在执行操作 2 时同时变空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.71875。

说明:

  • 0 <= n <= 10^9

思路

代码

性能

3363.最多可收集的水果数目

目标

有一个游戏，游戏由 n x n 个房间网格状排布组成。

给你一个大小为 n x n 的二维整数数组 fruits ，其中 fruits[i][j] 表示房间 (i, j) 中的水果数目。有三个小朋友 一开始 分别从角落房间 (0, 0) ，(0, n - 1) 和 (n - 1, 0) 出发。

每一位小朋友都会 恰好 移动 n - 1 次，并到达房间 (n - 1, n - 1) ：

  • 从 (0, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达 (i + 1, j + 1) ，(i + 1, j) 和 (i, j + 1) 房间之一（如果存在）。
  • 从 (0, n - 1) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i + 1, j - 1) ，(i + 1, j) 和 (i + 1, j + 1) 房间之一（如果存在）。
  • 从 (n - 1, 0) 出发的小朋友每次移动从房间 (i, j) 出发，可以到达房间 (i - 1, j + 1) ，(i, j + 1) 和 (i + 1, j + 1) 房间之一（如果存在）。

当一个小朋友到达一个房间时，会把这个房间里所有的水果都收集起来。如果有两个或者更多小朋友进入同一个房间，只有一个小朋友能收集这个房间的水果。当小朋友离开一个房间时，这个房间里不会再有水果。

请你返回三个小朋友总共 最多 可以收集多少个水果。

示例 1：

输入：fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
输出：100
解释：
这个例子中：
第 1 个小朋友（绿色）的移动路径为 (0,0) -> (1,1) -> (2,2) -> (3, 3) 。
第 2 个小朋友（红色）的移动路径为 (0,3) -> (1,2) -> (2,3) -> (3, 3) 。
第 3 个小朋友（蓝色）的移动路径为 (3,0) -> (3,1) -> (3,2) -> (3, 3) 。
他们总共能收集 1 + 6 + 11 + 1 + 4 + 8 + 12 + 13 + 14 + 15 = 100 个水果。

示例 2：

输入：fruits = [[1,1],[1,1]]
输出：4
解释：
这个例子中：
第 1 个小朋友移动路径为 (0,0) -> (1,1) 。
第 2 个小朋友移动路径为 (0,1) -> (1,1) 。
第 3 个小朋友移动路径为 (1,0) -> (1,1) 。
他们总共能收集 1 + 1 + 1 + 1 = 4 个水果。

说明：

  • 2 <= n == fruits.length == fruits[i].length <= 1000
  • 0 <= fruits[i][j] <= 1000

思路

有一个 n x n 排列的房间，房间中放有水果，fruits[i][j] 表示坐标为 (i, j) 的房间中的水果数量，有三个小朋友 A B C 同时从 (0, 0) (0, n - 1) (n - 1, 0) 出发，A 可以向 →、↓、↘ 走，B 可以向 ↙、↓、↘ 走，C 可以向 →、↗、↘ 走，每一个小朋友到达一个房间会带走所有水果，求三个小朋友从起点出发，恰好走 n - 1 步 到达 (n - 1, n - 1) 总共可以收集的水果数量。

// todo

代码

性能

3202.找出有效子序列的最大长度II

目标

给你一个整数数组 nums 和一个 正 整数 k 。

nums 的一个 子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列 ：

  • (sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x - 1]) % k

返回 nums 的 最长有效子序列 的长度。

示例 1：

输入：nums = [1,2,3,4,5], k = 2
输出：5
解释：
最长有效子序列是 [1, 2, 3, 4, 5] 。

示例 2：

输入：nums = [1,4,2,3,1,4], k = 3
输出：4
解释：
最长有效子序列是 [1, 4, 1, 4] 。

说明：

  • 2 <= nums.length <= 10^3
  • 1 <= nums[i] <= 10^7
  • 1 <= k <= 10^3

思路

找出数组 nums 的有效子序列的最大长度，有效子序列指相邻元素之和模 k 的值相等。

3201.找出有效子序列的最大长度I 是本题 k = 2 的特例。这个题目可能的组合有 k^2 种。

定义 dp[i][j] 表示子序列后两项模 k 的值为 i 和 j 的子序列长度。

代码


/**
 * @date 2025-07-16 10:18
 */
public class MaximumLength3202 {

    public int maximumLength(int[] nums, int k) {
        int[][] dp = new int[k][k];
        int res = 0;
        for (int num : nums) {
            int m = num % k;
            for (int i = 0; i < k; i++) {
                dp[i][m] = dp[m][i] + 1;
                res = Math.max(res, dp[i][m]);
            }
        }
        return res;
    }

}

性能

3201.找出有效子序列的最大长度I

目标

给你一个整数数组 nums。

nums 的子序列 sub 的长度为 x ，如果其满足以下条件，则称其为 有效子序列：

  • (sub[0] + sub[1]) % 2 == (sub[1] + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2

返回 nums 的 最长的有效子序列 的长度。

一个 子序列 指的是从原数组中删除一些元素（也可以不删除任何元素），剩余元素保持原来顺序组成的新数组。

示例 1：

输入： nums = [1,2,3,4]
输出： 4
解释：
最长的有效子序列是 [1, 2, 3, 4]。

示例 2：

输入： nums = [1,2,1,1,2,1,2]
输出： 6
解释：
最长的有效子序列是 [1, 2, 1, 2, 1, 2]。

示例 3：

输入： nums = [1,3]
输出： 2
解释：
最长的有效子序列是 [1, 3]。

说明：

  • 2 <= nums.length <= 2 * 10^5
  • 1 <= nums[i] <= 10^7

思路

找出有效子序列的最大长度，使得子序列中相邻元素和的奇偶性相同。

注意到有效子序列中奇数下标的奇偶性必须相同，同时偶数下标的奇偶性也必须相同。总共四种情况：奇偶、奇奇、偶奇、偶偶。

代码


/**
 * @date 2025-07-16 8:43
 */
public class MaximumLength3201 {

    public int maximumLength(int[] nums) {
        int res = 0;
        for (int a = 0; a <= 1; a++) {
            for (int b = 0; b <= 1; b++) {
                int l = 0;
                int[] p = new int[]{a, b};
                int k = 0;
                for (int num : nums) {
                    if (num % 2 == p[k]) {
                        l++;
                        k ^= 1;
                    }
                }
                res = Math.max(l, res);
            }
        }
        return res;
    }

}

性能

1900.最佳运动员的比拼回合

目标

n 名运动员参与一场锦标赛，所有运动员站成一排，并根据 最开始的 站位从 1 到 n 编号（运动员 1 是这一排中的第一个运动员，运动员 2 是第二个运动员，依此类推）。

锦标赛由多个回合组成（从回合 1 开始）。每一回合中，这一排从前往后数的第 i 名运动员需要与从后往前数的第 i 名运动员比拼，获胜者将会进入下一回合。如果当前回合中运动员数目为奇数，那么中间那位运动员将轮空晋级下一回合。

例如，当前回合中，运动员 1, 2, 4, 6, 7 站成一排

  • 运动员 1 需要和运动员 7 比拼
  • 运动员 2 需要和运动员 6 比拼
  • 运动员 4 轮空晋级下一回合

每回合结束后，获胜者将会基于最开始分配给他们的原始顺序（升序）重新排成一排。

编号为 firstPlayer 和 secondPlayer 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前，完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时，其中任意一个都有获胜的可能，因此你可以 裁定 谁是这一回合的获胜者。

给你三个整数 n、firstPlayer 和 secondPlayer 。返回一个由两个值组成的整数数组，分别表示两位最佳运动员在本场锦标赛中比拼的 最早 回合数和 最晚 回合数。

示例 1：

输入：n = 11, firstPlayer = 2, secondPlayer = 4
输出：[3,4]
解释：
一种能够产生最早回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：2, 3, 4, 5, 6, 11
回合 3：2, 3, 4
一种能够产生最晚回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：1, 2, 3, 4, 5, 6
回合 3：1, 2, 4
回合 4：2, 4

示例 2：

输入：n = 5, firstPlayer = 1, secondPlayer = 5
输出：[1,1]
解释：两名最佳运动员 1 和 5 将会在回合 1 进行比拼。
不存在使他们在其他回合进行比拼的可能。

说明：

  • 2 <= n <= 28
  • 1 <= firstPlayer < secondPlayer <= n

思路

代码

性能

1751.最多可以参加的会议数目II

目标

给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和 。

示例 1：

输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。

示例 2：

输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。

示例 3：

输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。

说明：

  • 1 <= k <= events.length
  • 1 <= k * events.length <= 10^6
  • 1 <= startDayi <= endDayi <= 10^9
  • 1 <= valuei <= 10^6

思路

从 n 个会议中选择 k 个日期不冲突的参加，求参加会议的最大价值之和。

与 1353.最多可以参加的会议数目 不同之处在于必须从头到尾全程参会，并且最多参加 k 个。

定义 dp[i][k] 表示前 i - 1 个会议至多参加 k 个所能获得的最大价值。i == 0 表示没有参加任何会议。

按照结束时间排序，如果选择当前会议，则需要找到最后一个结束时间小于当前开始时间的下标 j，可以使用二分查找。

代码


/**
 * @date 2025-07-08 8:47
 */
public class MaxValue1751 {

    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);
        int n = events.length;
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i < n; i++) {
            int prev = find(events, events[i][0]);
            for (int j = 1; j <= k; j++) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[prev + 1][j - 1] + events[i][2]);
            }
        }
        return dp[n][k];
    }

    public int find(int[][] events, int target) {
        int r = events.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (events[mid][1] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
            mid = l + (r - l) / 2;
        }
        return r;
    }

}

性能

3333.找到初始输入字符串II

目标

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。

给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。同时给你一个 正 整数 k ，表示一开始 Alice 输入字符串的长度 至少 为 k 。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

输入：word = "aabbccdd", k = 7
输出：5
解释：
可能的字符串包括："aabbccdd" ，"aabbccd" ，"aabbcdd" ，"aabccdd" 和 "abbccdd" 。

示例 2：

输入：word = "aabbccdd", k = 8
输出：1
解释：
唯一可能的字符串是 "aabbccdd" 。

示例 3：

输入：word = "aaabbb", k = 3
输出：8

说明：

  • 1 <= word.length <= 5 * 10^5
  • word 只包含小写英文字母。
  • 1 <= k <= 2000

思路

有一个字符串，其中可能存在字符由于按键失灵没有及时抬起，导致该字符被输入多次。求原始字符串的总方案数，已知原字符串长度至少为 k。

与 3330.找到初始输入字符串I 相比取消了至多一个错误的限制，增加了原始字符的长度限制。

// todo

代码

性能

2616.最小化数对的最大差值

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的 最大值 最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的 绝对值 。

请你返回 p 个下标对对应数值 最大差值 的 最小值 。

示例 1：

输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

示例 2：

输入：nums = [4,2,1,2], p = 1
输出：0
解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。

说明：

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= p <= (nums.length)/2

思路

取 p 个不包含相同下标的下标对，使这 p 个下标对的绝对差的最大值最小。

最小化最大值，优先考虑二分查找。问题是如何判断绝对差小于当前值的数对个数。

参考 2560.打家劫舍IV，可以使用动态规划或者贪心。

关键是贪心策略，只要相邻元素的绝对差小于二分的最大绝对差就是可选的。

代码


/**
 * @date 2025-06-13 0:09
 */
public class MinimizeMax2616 {

    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int r = nums[nums.length - 1] - nums[0];
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (check(nums, p, mid)) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            mid = l + (r - l) / 2;
        }
        return l;
    }

    public boolean check(int[] nums, int p, int cur) {
        int n = nums.length;
        for (int i = 1; i < n && p > 0; i++) {
            if (nums[i] - nums[i - 1] <= cur) {
                i++;
                p--;
            }
        }
        return p == 0;
    }

}

性能

3068.最大节点价值之和

目标

给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ，其中 nums[i] 表示节点 i 的 价值 。

Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：

  • 选择连接节点 u 和 v 的边 [u, v] ，并将它们的值更新为：
    • nums[u] = nums[u] XOR k
    • nums[v] = nums[v] XOR k

请你返回 Alice 通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。

示例 1：

输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：Alice 可以通过一次操作得到最大价值和 6 ：
- 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。
所有节点价值之和为 2 + 2 + 2 = 6 。
6 是可以得到最大的价值之和。

示例 2：

输入：nums = [2,3], k = 7, edges = [[0,1]]
输出：9
解释：Alice 可以通过一次操作得到最大和 9 ：
- 选择边 [0,1] 。nums[0] 变为：2 XOR 7 = 5 ，nums[1] 变为：3 XOR 7 = 4 ，数组 nums 变为：[2,3] -> [5,4] 。
所有节点价值之和为 5 + 4 = 9 。
9 是可以得到最大的价值之和。

示例 3：

输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
输出：42
解释：Alice 不需要执行任何操作，就可以得到最大价值之和 42 。

说明：

  • 2 <= n == nums.length <= 2 * 10^4
  • 1 <= k <= 10^9
  • 0 <= nums[i] <= 10^9
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • 输入保证 edges 构成一棵合法的树。

思路

// todo

代码

性能