标签： 动态规划

目标

给你一个字符串 s 和一个 正 整数 k 。

从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：

• 每个子字符串的长度 至少 为 k 。
• 每个子字符串是一个 回文串 。

返回最优方案中能选择的子字符串的 最大 数目。

子字符串 是字符串中一个连续的字符序列。

示例 1 ：

输入：s = "abaccdbbd", k = 3
输出：2
解释：可以选择 s = "abaccdbbd" 中斜体加粗的子字符串。"aba" 和 "dbbd" 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。

示例 2 ：

输入：s = "adbcda", k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。

说明：

• 1 <= k <= s.length <= 2000
• s 仅由小写英文字母组成

思路

返回字符串 s 中长度 至少 为 k 的不重叠回文子串的最大个数。

定义 dp[i] 表示 s[i, n - 1] 中长度为 k 的不重叠回文子串的最大数目，

• 如果不选 s[i]，dp[i] = dp[i + 1]
• 如果选择 s[i]，枚举终点 j，使得 j - i + 1 >= k，如果 s[i, j] 是回文，dp[i] = max(dp[i], 1 + dp[j + 1]))

需要快速判断子串是否是回文，可以预处理。

代码

/**
 * @date 2026-09-15 9:24
 */
public class MaxPalindromes2472 {

    public int maxPalindromes(String s, int k) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            isPalindrome[i][i] = true;
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                isPalindrome[l--][r++] = true;
            }
            l = i - 1;
            r = i;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
                isPalindrome[l--][r++] = true;
            }
        }
        int[] dp = new int[n + 1];
        for (int i = n - k; i >= 0; i--) {
            dp[i] = dp[i + 1];
            for (int j = n - 1; j >= i + k - 1; j--) {
                if (isPalindrome[i][j]) {
                    dp[i] = Math.max(dp[i], 1 + dp[j + 1]);
                }
            }
        }
        return dp[0];
    }

}

性能

目标

Alice 和 Bob 继续他们的石子游戏。几堆石子 排成一行 ，每堆石子都对应一个得分，由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子，Alice 总是先开始。在每个玩家的回合中，该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。

比赛的目标是决出最高分，得分最高的选手将会赢得比赛，比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。

如果 Alice 赢了就返回 "Alice" ，Bob 赢了就返回 "Bob"，分数相同返回 "Tie" 。

示例 1：

输入：values = [1,2,3,7]
输出："Bob"
解释：Alice 总是会输，她的最佳选择是拿走前三堆，得分变成 6 。但是 Bob 的得分为 7，Bob 获胜。

示例 2：

输入：values = [1,2,3,-9]
输出："Alice"
解释：Alice 要想获胜就必须在第一个回合拿走前三堆石子，给 Bob 留下负分。
如果 Alice 只拿走第一堆，那么她的得分为 1，接下来 Bob 拿走第二、三堆，得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆，输掉比赛。
如果 Alice 拿走前两堆，那么她的得分为 3，接下来 Bob 拿走第三堆，得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆，同样会输掉比赛。
注意，他们都应该采取 最优策略 ，所以在这里 Alice 将选择能够使她获胜的方案。

示例 3：

输入：values = [1,2,3,6]
输出："Tie"
解释：Alice 无法赢得比赛。如果她决定选择前三堆，她可以以平局结束比赛，否则她就会输。

说明：

• 1 <= stoneValue.length <= 5 * 10^4
• -1000 <= stoneValue[i] <= 1000

思路

几堆石子排成一排，stoneValue[i] 表示第 i 堆石子的个数。Alice 与 Bob 轮流取石子，Alice 先取，每次可以从剩余的石子堆中取走前 1、2 或者 3 堆石子，直到石子均被取走。返回结束时取走石子最多的玩家姓名，如果相同则返回 Tie。

定义 dp[i] 表示剩余 [i, n - 1] 堆石子，先手与后手所能获得的石子个数之差的最大值。dp[i] = max(sumj - dp[j + 1])，其中 j ∈ [i, min(i + 2, n - 1)]，sumj 表示 [i, j] 的石子堆数量之和。倒序遍历，初始化 dp[n] = 0, dp[n - 1] = stoneValue[n - 1]。

代码

/**
 * @date 2026-08-03 15:22
 */
public class StoneGameIII1406 {

    public String stoneGameIII(int[] stoneValue) {
        int n = stoneValue.length;
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[n] = 0;
        dp[n - 1] = stoneValue[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            int sum = 0;
            for (int j = i; j < Math.min(n, i + 3); j++) {
                sum += stoneValue[j];
                dp[i] = Math.max(dp[i], sum - dp[j + 1]);
            }
        }
        if (dp[0] == 0) {
            return "Tie";
        }
        return dp[0] > 0 ? "Alice" : "Bob";
    }
}

性能