标签： 动态规划

2140.解决智力问题

目标

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：

  • 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
  • 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

说明：

  • 1 <= questions.length <= 10^5
  • questions[i].length == 2
  • 1 <= pointsi, brainpoweri <= 10^5

思路

有一个二维数组 questions 表示一场考试里的一系列题目，questions[i][0] 表示解决第 i 题能获得的分数，questions[i][1] 表示解决该题需要消耗的脑力，即解决了第 i 题后，i 后面的 questions[i][1] 个题目都无法解决。返回在该场考试所能获得的最高分。

这个题有许多值得思考的地方，有空整理一下。//todo

代码


/**
 * @date 2025-04-01 8:47
 */
public class MostPoints2140 {

    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int j = Math.min(i + questions[i][1] + 1, n);
            dp[i] = Math.max(dp[i + 1], dp[j] + questions[i][0]);
        }
        return dp[0];
    }

}

性能

2712.使所有字符相等的最小成本

目标

给你一个下标从 0 开始、长度为 n 的二进制字符串 s ，你可以对其执行两种操作：

  • 选中一个下标 i 并且反转从下标 0 到下标 i（包括下标 0 和下标 i ）的所有字符，成本为 i + 1 。
  • 选中一个下标 i 并且反转从下标 i 到下标 n - 1（包括下标 i 和下标 n - 1 ）的所有字符，成本为 n - i 。

返回使字符串内所有字符 相等 需要的 最小成本 。

反转 字符意味着：如果原来的值是 '0' ，则反转后值变为 '1' ，反之亦然。

示例 1：

输入：s = "0011"
输出：2
解释：执行第二种操作，选中下标 i = 2 ，可以得到 s = "0000" ，成本为 2 。可以证明 2 是使所有字符相等的最小成本。

示例 2：

输入：s = "010101"
输出：9
解释：执行第一种操作，选中下标 i = 2 ，可以得到 s = "101101" ，成本为 3 。
执行第一种操作，选中下标 i = 1 ，可以得到 s = "011101" ，成本为 2 。
执行第一种操作，选中下标 i = 0 ，可以得到 s = "111101" ，成本为 1 。
执行第二种操作，选中下标 i = 4 ，可以得到 s = "111110" ，成本为 2 。
执行第二种操作，选中下标 i = 5 ，可以得到 s = "111111" ，成本为 1 。
使所有字符相等的总成本等于 9 。可以证明 9 是使所有字符相等的最小成本。

说明：

  • 1 <= s.length == n <= 10^5
  • s[i] 为 '0' 或 '1'

思路

有一个二进制字符串，每次操作可以反转前缀 0 ~ i，成本是 i + 1，也可以反转后缀 i ~ n - 1，成本是 n - i。求使字符串所有字符相等的最小成本。

如何操作才能使字符相等？相等字符是 0 还是 1？操作哪边才能使成本最小？

关键点是想清楚与是 0 还是 1 没有关系，只要相邻的元素值不同，就必须要反转，无非是考虑反转前缀还是后缀，每次操作只影响相邻的元素关系。

代码


/**
 * @date 2025-03-27 1:33
 */
public class MinimumCost2712 {

    public long minimumCost(String s) {
        int n = s.length();
        long res = 0;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != s.charAt(i - 1)) {
                // i 表示反转 0 ~ i - 1，n - i 表示反转 i ~ n - 1
                res += Math.min(i, n - i);
            }
        }
        return res;
    }
}

性能

2272.最大波动的子字符串

目标

字符串的 波动 定义为子字符串中出现次数 最多 的字符次数与出现次数 最少 的字符次数之差。

给你一个字符串 s ，它只包含小写英文字母。请你返回 s 里所有 子字符串的 最大波动 值。

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

示例 1：

输入：s = "aababbb"
输出：3
解释：
所有可能的波动值和它们对应的子字符串如以下所示：
- 波动值为 0 的子字符串："a" ，"aa" ，"ab" ，"abab" ，"aababb" ，"ba" ，"b" ，"bb" 和 "bbb" 。
- 波动值为 1 的子字符串："aab" ，"aba" ，"abb" ，"aabab" ，"ababb" ，"aababbb" 和 "bab" 。
- 波动值为 2 的子字符串："aaba" ，"ababbb" ，"abbb" 和 "babb" 。
- 波动值为 3 的子字符串 "babbb" 。
所以，最大可能波动值为 3 。

示例 2：

输入：s = "abcde"
输出：0
解释：
s 中没有字母出现超过 1 次，所以 s 中每个子字符串的波动值都是 0 。

说明：

  • 1 <= s.length <= 10^4
  • s 只包含小写英文字母。

思路

//todo

代码

性能

2597.美丽子集的数目

目标

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

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

示例 1：

输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

示例 2：

输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。

说明：

  • 1 <= nums.length <= 18
  • 1 <= nums[i], k <= 1000

思路

返回数组的美丽子序列个数，美丽指子序列中任意两个元素的差的绝对值不等于 k。

由于数组长度不大，可以回溯枚举子序列，并针对每一子序列，两两比较，判断差的绝对值是否等于 k。

更好的处理方法是使用哈希表记录元素的出现次数，回溯枚举子序列时直接判断当前元素加减 k 的绝对值是否存在于哈希表中。

代码


/**
 * @date 2025-03-07 0:09
 */
public class BeautifulSubsets2597 {

    public int beautifulSubsets(int[] nums, int k) {
        return dfs(0, new ArrayList<>(), nums, k);
    }

    public int dfs(int index, List<Integer> path, int[] nums, int k) {
        if (index == nums.length) {
            return path.size() > 0 ? 1 : 0;
        }
        int res = 0;
        res += dfs(index + 1, path, nums, k);
        for (Integer num : path) {
            if (Math.abs(num - nums[index]) == k) {
                return res;
            }
        }
        path.add(nums[index]);
        res += dfs(index + 1, path, nums, k);
        path.remove(path.size() - 1);
        return res;
    }

}

性能

1745.分割回文串IV

目标

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

说明：

  • 3 <= s.length <= 2000
  • s​​​​​​ 只包含小写英文字母。

思路

判断能否将给定字符串分割成三个非空回文子串。

核心逻辑：

  • 计算所有子串是否是回文。
  • 从起点 i = 0 开始，枚举所有终点 j，如果是 s[i~j] 是回文，k-- 接着以 j + 1 为起点继续递归搜索。
  • 结束条件是 i == s.length() || k < 0，如果 k == 0 返回 true。

代码


/**
 * @date 2025-03-04 15:58
 */
public class CheckPartitioning1745 {

    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (boolean[] row : isPalindrome) {
            Arrays.fill(row, true);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];
            }
        }
        char[][] mem = new char[n][4];
        return dfs(0, 3, isPalindrome, s, mem);
    }

    public boolean dfs(int i, int k, boolean[][] isPalindrome, String s, char[][] mem) {
        int n = s.length();
        if (i == n || k < 0) {
            return k == 0;
        }
        if (mem[i][k] != '\u0000') {
            return mem[i][k] == 'T';
        }
        boolean res = false;
        for (int j = i; j < n; j++) {
            if (isPalindrome[i][j]) {
                res = res || dfs(j + 1, k - 1, isPalindrome, s, mem);
            }
        }
        mem[i][k] = res ? 'T' : 'F';
        return res;
    }

}

性能

1278.分割回文串III

目标

给你一个由小写字母组成的字符串 s，和一个整数 k。

请你按下面的要求分割字符串：

  • 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
  • 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。

请返回以这种方式分割字符串所需修改的最少字符数。

示例 1：

输入：s = "abc", k = 2
输出：1
解释：你可以把字符串分割成 "ab" 和 "c"，并修改 "ab" 中的 1 个字符，将它变成回文串。

示例 2：

输入：s = "aabbc", k = 3
输出：0
解释：你可以把字符串分割成 "aa"、"bb" 和 "c"，它们都是回文串。

示例 3：

输入：s = "leetcode", k = 8
输出：0

说明：

  • 1 <= k <= s.length <= 100
  • s 中只含有小写英文字母。

思路

将字符串 s 分割成 k 个非空回文子串，允许修改字符中的任意字符，求修改字符的最小次数。

需要将字符串分割成 k 份并且每一份都是回文。我们需要暴力枚举所有可能的分法，并求得每种分法的修改次数，取其最小值。

核心逻辑：

  • 计算所有子串变为回文的修改次数，ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;。由于需要从 i + 1 转移过来，所以外层倒序。初始化数组所有值为 0，外层从倒数第二个开始，内层从 i + 1 开始。
  • 从起点 i = 0 开始，枚举所有终点 j，无论 s[i~j] 是否是回文，我们直接加上 ops[i][j]，k-- 接着以 j + 1 为起点继续递归搜索。
  • 结束条件：
    • i 未到结尾 k 先减为 0，不符合要求，返回 INF，可以取 0x3f3f3f3f
    • i == s.length()，如果 k == 0 返回 0，否则说明分割的子串没有 k 个，不符合题意返回 INF

代码


/**
 * @date 2025-03-03 8:52
 */
public class PalindromePartition1278 {

    public int palindromePartition(String s, int k) {
        int n = s.length();
        int[][] ops = new int[n][n];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                ops[i][j] = s.charAt(i) == s.charAt(j) ? ops[i + 1][j - 1] : ops[i + 1][j - 1] + 1;
            }
        }
        int[][] mem = new int[n][k + 1];
        for (int[] row : mem) {
            Arrays.fill(row, -1);
        }
        return dfs(0, k, s, ops, mem);
    }

    public int dfs(int i, int k, String s, int[][] ops, int[][] mem) {
        int n = s.length();
        if (i == n) {
            return k > 0 ? 0x3f3f3f3f : 0;
        }
        if (k == 0) {
            return 0x3f3f3f3f;
        }
        if (mem[i][k] != -1) {
            return mem[i][k];
        }
        int res = Integer.MAX_VALUE;
        for (int j = i; j < n; j++) {
            res = Math.min(res, ops[i][j] + dfs(j + 1, k - 1, s, ops, mem));
        }
        mem[i][k] = res;
        return res;
    }

}

性能

132.分割回文串II

目标

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

说明：

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

思路

计算将字符串分割成回文子串的最小分割次数。

定义 dp[i] 表示前 i + 1 个字符的最小分割次数，如果 [0, i] 个字符已经是回文，无需切割，切割次数为 0。否则，需要枚举起点 j，如果 [j, i] 是回文，dp[i] = Math.min(dp[j - 1] + 1)。

预处理 [i, j] 是否是回文，isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1]，由于状态由 i + 1 转换而来，外层要倒序，内层正序或倒序都可以。

代码


/**
 * @date 2025-03-02 0:10
 */
public class MinCut132 {

    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPalindrome = new boolean[n][n];
        for (boolean[] row : isPalindrome) {
            Arrays.fill(row, true);
        }
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i + 1][j - 1];
            }
        }
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            if (isPalindrome[0][i]) {
                continue;
            }
            int res = Integer.MAX_VALUE;
            for (int j = 1; j <= i; j++) {
                if (isPalindrome[j][i]) {
                    res = Math.min(res, dp[j - 1] + 1);
                }
            }
            dp[i] = res;
        }
        return dp[n - 1];
    }

}

性能

131.分割回文串

目标

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

说明：

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

思路

返回将字符串划分为回文子串的所有可能方案。

定义 dp[i] 表示将前 i + 1 个字符划分为回文子串的所有可能方案。dp[i] 可以取 dp[i - 1] 每种方案的最后一或两个回文，判断能否与当前字符合并成新的回文。

代码


/**
 * @date 2025-03-01 20:16
 */
public class Partition131 {

    public List<List<String>> partition(String s) {
        int n = s.length();
        List<List<String>>[] dp = new List[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new ArrayList<>();
        }
        char[] chars = s.toCharArray();
        dp[0].add(new ArrayList<>());
        dp[0].get(0).add((String.valueOf(chars[0])));
        for (int i = 1; i < n; i++) {
            dp[i] = new ArrayList<>();
            for (List<String> list : dp[i - 1]) {
                // 首先将单个字符加入
                List<String> tmp = new ArrayList<>(list);
                tmp.add(String.valueOf(chars[i]));
                dp[i].add(tmp);
                String cur = String.valueOf(chars[i]);
                // 判断能与最后一个回文合并成新的回文
                if (list.get(list.size() - 1).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 1));
                    tmp.add(list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
                // 判断能否与后两个回文合并成新的回文
                if (list.size() > 1 && list.get(list.size() - 2).equals(cur)) {
                    tmp = new ArrayList<>(list.subList(0, list.size() - 2));
                    tmp.add(list.get(list.size() - 2) + list.get(list.size() - 1) + cur);
                    dp[i].add(tmp);
                }
            }
        }
        return dp[n - 1];
    }

}

性能

时间复杂度 O(n * 2^n)，假设每个字符之间都有一个逗号，考虑选或不选共有 2^(n - 1) 种划分。前 i + 1 个 字符有 2^i 种划分， 等比数列求和得到 2^n - 1。

2209.用地毯覆盖后的最少白色砖块

目标

给你一个下标从 0 开始的 二进制 字符串 floor ，它表示地板上砖块的颜色。

  • floor[i] = '0' 表示地板上第 i 块砖块的颜色是 黑色 。
  • floor[i] = '1' 表示地板上第 i 块砖块的颜色是 白色 。

同时给你 numCarpets 和 carpetLen 。你有 numCarpets 条 黑色 的地毯，每一条 黑色 的地毯长度都为 carpetLen 块砖块。请你使用这些地毯去覆盖砖块，使得未被覆盖的剩余 白色 砖块的数目 最小 。地毯相互之间可以覆盖。

请你返回没被覆盖的白色砖块的 最少 数目。

示例 1：

输入：floor = "10110101", numCarpets = 2, carpetLen = 2
输出：2
解释：
上图展示了剩余 2 块白色砖块的方案。
没有其他方案可以使未被覆盖的白色砖块少于 2 块。

示例 2：

输入：floor = "11111", numCarpets = 2, carpetLen = 3
输出：0
解释：
上图展示了所有白色砖块都被覆盖的一种方案。
注意，地毯相互之间可以覆盖。

说明：

  • 1 <= carpetLen <= floor.length <= 1000
  • floor[i] 要么是 '0' ，要么是 '1' 。
  • 1 <= numCarpets <= 1000

思路

有 floor.length 块一字排列的砖，floor[i] 的值表示砖的颜色，0 代表黑色，1 代表白色。另有 numCarpets 条长度为 carpetLen 的地毯。求使用地毯覆盖砖块剩余 白色 砖块的最小数目。

假设白色砖块有 k 个，那么可行的方案数有 C(k, numCarpets) 种，即选 k 块白砖为起点覆盖地毯。

//todo

代码

性能

1742.盒子中小球的最大数量

目标

你在一家生产小球的玩具厂工作，有 n 个小球，编号从 lowLimit 开始，到 highLimit 结束（包括 lowLimit 和 highLimit ，即 n == highLimit - lowLimit + 1）。另有无限数量的盒子，编号从 1 到 infinity 。

你的工作是将每个小球放入盒子中，其中盒子的编号应当等于小球编号上每位数字的和。例如，编号 321 的小球应当放入编号 3 + 2 + 1 = 6 的盒子，而编号 10 的小球应当放入编号 1 + 0 = 1 的盒子。

给你两个整数 lowLimit 和 highLimit ，返回放有最多小球的盒子中的小球数量。如果有多个盒子都满足放有最多小球，只需返回其中任一盒子的小球数量。

示例 1：

输入：lowLimit = 1, highLimit = 10
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：2 1 1 1 1 1 1 1 1 0  0  ...
编号 1 的盒子放有最多小球，小球数量为 2 。

示例 2：

输入：lowLimit = 5, highLimit = 15
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 ...
小球数量：1 1 1 1 2 2 1 1 1 0  0  ...
编号 5 和 6 的盒子放有最多小球，每个盒子中的小球数量都是 2 。

示例 3：

输入：lowLimit = 19, highLimit = 28
输出：2
解释：
盒子编号：1 2 3 4 5 6 7 8 9 10 11 12 ...
小球数量：0 1 1 1 1 1 1 1 1 2  0  0  ...
编号 10 的盒子放有最多小球，小球数量为 2 。

说明：

  • 1 <= lowLimit <= highLimit <= 10^5

思路

有 n 个编号从 lowLimit 到 highLimit 的小球，同时有编号 [1, +∞] 的盒子。将小球放入它编号数位之和对应的盒子中，求放有最多小球的盒子中的小球数量。

暴力做法是针对每一个数字计算其数位之和。时间复杂度为 O(l * n)。l 表示数字的长度，最大 6 位数字，总规模为 6 * 10^5 可行。

注意到编号是连续的，如果编号没有进位，那么盒号加 1；如果编号进位，盒号进位加 1，还要减去原来编号末尾的 9，有几个 9 就减几个。省去了每一个数的数位求和。

代码


/**
 * @date 2025-02-13 0:57
 */
public class CountBalls1742 {

    public int countBalls_v2(int lowLimit, int highLimit) {
        int boxNo = 0;
        int num = lowLimit;
        while (num > 0) {
            boxNo += num % 10;
            num /= 10;
        }
        int[] cnt = new int[46];
        for (int i = lowLimit; i <= highLimit; i++) {
            cnt[boxNo++]++;
            int tmp = i;
            while (tmp % 10 == 9) {
                boxNo -= 9;
                tmp /= 10;
            }
        }
        return Arrays.stream(cnt).max().getAsInt();
    }

    public int countBalls(int lowLimit, int highLimit) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = lowLimit; i <= highLimit; i++){
            int sum = 0;
            int num = i;
            while(num > 0){
                sum += num % 10;
                num /= 10;
            }
            map.merge(sum, 1, Integer::sum);
        }
        return map.values().stream().max(Integer::compareTo).orElse(0);
    }
}

性能