664. 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

  • 打印机每次只能打印由 同一个字符 组成的序列。

  • 每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。


    给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
    示例 1：
    输入：s = “aaabbb” 输出：2 解释：首先打印 “aaa” 然后打印 “bbb”。
    示例 2：
    输入：s = “aba” 输出：2 解释：首先打印 “aaa” 然后在第二个位置打印 “b” 覆盖掉原来的字符 ‘a’。

提示：

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

思路：
区间DP
f[i][j]表示打印[i, j]这段区间的所有方案
属性：最小值

证明：第一步打印总可以转换为打印区间首字符(或尾字符)，并保证后续继续打印到整个区间与目标区间一致的方案的打印次数一定能与最小打印次数相同。

  1. 如果最优方案第一步就是打印首字符(或尾字符)，结论显然成立
  2. 如果最优方案第一步不是打印首字符(或尾字符)，证明可以将打印首字符(或尾字符)的那一步转换到第一步且结果不变
    1. 如果打印首字符时区间长度仅包含首字符本身，即[i, i]，将这一步挪至第一步对其它操作无任何影响
    2. 如果打印首字符时区间为[i, k]时，若[i, k]这一段字符全部相同，将这一步操作挪至任意步对其它操作无任何影响；若这一段混有其它字符c，说明后续需要继续打印使其变为目标字符，此时又有两种情况，打印c时的操作区间完全在(i, k)中以及打印c时操作区间包含k并可能延伸至k的右侧。如果是第一种情况将修改首字符的操作放至第一步对其完全没有影响。如果是第二种情况，在覆盖首字符时，其区间仅仅只需延申至c所在下标之前即可，因为c到k这一段还会被修改，故仍可以将打印首字符的操作放至第一步

状态转移：
f[i][j] = Math.min(f[i][j], f[i][k - 1] + f[k + 1][j]), s[i] == s[k]
f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j]), s[i] != s[k]

  1. class Solution {
  2.     public int strangePrinter(String s) {
  3.         int n = s.length();
  4.         int[][] f = new int[n + 1][n + 1];
  5.         for (int i = n - 1; i >= 0; i--) {
  6.             Arrays.fill(f[i], 0x3f3f3f3f);
  7.             f[i][i] = 1;
  8.             f[i + 1][i] = 0;
  9.         }
  10.         for (int len = 2; len <= n; len++) {
  11.             for (int l = 0; l + len - 1 < n; l ++) {
  12.                 int r = l + len - 1;
  13.                 f[l][r] = 1 + f[l + 1][r];
  14.                 for (int i = l + 1; i <= r; i++) {
  15.                     if (s.charAt(i) == s.charAt(l)) {
  16.                         f[l][r] = Math.min(f[l][r], f[l][i - 1] + f[i + 1][r]);
  17.                     } else {
  18.                         f[l][r] = Math.min(f[l][r], f[l][i] + f[i + 1][r]);
  19.                     }
  20.                 }
  21.             }
  22.         }
  23.         return f[0][n - 1];
  24.     }
  25. }

546. 移除盒子

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。
你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。
返回 你能获得的最大积分和 。

示例 1：
输入：boxes = [1,3,2,2,2,3,4,3,1] 输出：23 解释： [1, 3, 2, 2, 2, 3, 4, 3, 1] ——> [1, 3, 3, 4, 3, 1] (33=9 分) ——> [1, 3, 3, 3, 1] (11=1 分) ——> [1, 1] (33=9 分) ——> [] (22=4 分)
示例 2：
输入：boxes = [1,1,1] 输出：9
示例 3：
输入：boxes = [1] 输出：1

提示：

  • 1 <= boxes.length <= 100
  • 1 <= boxes[i] <= 100

思路：
区间DP，只不过得再加一维
状态表示：f[i][j][k]表示区间[i, j]且s[i]被最后删除，长度为k的所有删除方案
属性：最大得分
状态转移：
首先规定g[i][j] = max(f[i][j][k]), k ∈ [1, j - i + 1]
第一种情况，最后删除的只有s[i]本身，f[i][j][1] = g[i + 1][j] + 1
第二种情况，最后删除的除了s[i]外，还有某个以s[p] == s[i]为起始的子序列
这样整个[i, j]被分为两部分[i + 1, p - 1], i ∩ [p, j]
转移为f[i, j][c + 1] = max(f[i][j][c + 1], g[i + 1][p - 1] + f[p][j][c] - c * c + (c + 1) * (c + 1)), c ∈ [1, j - p + 1] && f[p][j][c] != 0

  1. class Solution {
  2.     public int removeBoxes(int[] boxes) {
  3.         int n = boxes.length;
  4.         int[][][] f = new int[n + 1][n + 1][n + 1];
  5.         int[][] g = new int[n + 1][n + 1];
  6.         int[] ne = new int[n];
  7.         Arrays.fill(ne, -1);
  8.         int[] idx = new int[110];
  9.         Arrays.fill(idx, -1);
  11.         // 预处理，快速找到相同字符的下一位置
  12.         for (int i = n - 1; i >= 0; i--) {
  13.             ne[i] = idx[boxes[i]];
  14.             idx[boxes[i]] = i;
  15.         }
  17.         for (int len = 1; len <= n; len++) {
  18.             for (int l = 0; l + len - 1 < n; l++) {
  19.                 int r = l + len - 1;
  20.                 if (len == 1) {
  21.                     f[l][r][1] = g[l][r] = 1;
  22.                 } else {
  23.                     f[l][r][1] = g[l + 1][r] + 1;
  24.                     for (int i = ne[l]; i <= r && i != -1; i = ne[i]) {
  25.                         for (int j = 1; j <= r - i + 1; j++)
  26.                             if (f[i][r][j] != 0)
  27.                                 f[l][r][j + 1] = Math.max(f[l][r][j + 1], g[l + 1][i - 1] + f[i][r][j] - j * j + (j + 1) * (j + 1));
  28.                     }
  30.                     for (int j = 1; j <= r - l + 1; j++)
  31.                         g[l][r] = Math.max(f[l][r][j], g[l][r]);
  32.                 }
  33.             }
  34.         }
  35.         return g[0][n - 1];
  36.     }
  37. }

486. 预测赢家

给你一个整数数组 nums 。玩家 1 和玩家 2 基于这个数组设计了一个游戏。
玩家 1 和玩家 2 轮流进行自己的回合，玩家 1 先手。开始时，两个玩家的初始分值都是 0 。每一回合，玩家从数组的任意一端取一个数字（即，nums[0] 或 nums[nums.length - 1]），取到的数字将会从数组中移除（数组长度减 1 ）。玩家选中的数字将会加到他的得分上。当数组中没有剩余数字可取时，游戏结束。
如果玩家 1 能成为赢家，返回 true 。如果两个玩家得分相等，同样认为玩家 1 是游戏的赢家，也返回 true 。你可以假设每个玩家的玩法都会使他的分数最大化。

示例 1：
输入：nums = [1,5,2] 输出：false 解释：一开始，玩家 1 可以从 1 和 2 中进行选择。 如果他选择 2（或者 1 ），那么玩家 2 可以从 1（或者 2 ）和 5 中进行选择。如果玩家 2 选择了 5 ，那么玩家 1 则只剩下 1（或者 2 ）可选。 所以，玩家 1 的最终分数为 1 + 2 = 3，而玩家 2 为 5 。 因此，玩家 1 永远不会成为赢家，返回 false 。
示例 2：
输入：nums = [1,5,233,7] 输出：true 解释：玩家 1 一开始选择 1 。然后玩家 2 必须从 5 和 7 中进行选择。无论玩家 2 选择了哪个，玩家 1 都可以选择 233 。 最终，玩家 1（234 分）比玩家 2（12 分）获得更多的分数，所以返回 true，表示玩家 1 可以成为赢家。

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 107

思路：
这也能区间DP我是没想到的
状态定义：f[i][j]表示区间[i, j]先手玩家能获得的最大分数减去对手能获得的最大分数
转移：f[i][j] = max(nums[i] - f[i + 1][j], nums[j] - f[i][j - 1] 若i != j
f[i][j] = nums[i] 若i == j

  1. class Solution {
  2.     public boolean PredictTheWinner(int[] nums) {
  3.         int n = nums.length;
  4.         int[][] f = new int[n][n];
  6.         for (int len = 1; len <= n; len ++) {
  7.             for (int l = 0; l + len - 1 < n; l ++) {
  8.                 int r = l + len - 1;
  9.                 if (len == 1)
  10.                     f[l][r] = nums[l];
  11.                 else 
  12.                     f[l][r] = Math.max(nums[l] - f[l + 1][r], nums[r] - f[l][r - 1]);
  13.             }
  14.         }
  15.         return f[0][n - 1] >= 0;
  16.     }
  17. }

1771. 由子序列构造的最长回文串的长度

难点在于如何判断非空

  1. class Solution {
  2.     public int longestPalindrome(String word1, String word2) {
  3.         return deal(word1 + word2, word1.length());
  4.     }
  6.     int deal(String s, int pre) {
  7.         int n = s.length();
  8.         char[] ch = s.toCharArray();
  9.         int[][] f = new int[n][n];
  11.         int max = 0;
  12.         for (int len = 1; len <= n; len++) {
  13.             for (int l = 0; l + len - 1 < n; l++) {
  14.                 int r = l + len - 1;
  15.                 if (len == 1)
  16.                     f[l][r] = 1;
  17.                 else if (len == 2)
  18.                     f[l][r] = ch[l] == ch[r] ? 2 : 1;
  19.                 else {
  20.                     f[l][r] = Math.max(f[l + 1][r], f[l][r - 1]);
  21.                     if (ch[l] == ch[r])
  22.                         f[l][r] = Math.max(f[l][r], f[l + 1][r - 1] + 2);
  23.                 }
  25.                 // 此处判断非空
  26.                 if (ch[l] == ch[r] && l < pre && r >= pre)
  27.                     max = Math.max(max, f[l][r]);
  28.             }
  29.         }
  30.         return max;
  31.     }
  32. }

730. 统计不同回文子序列

给定一个字符串 s，返回 s 中不同的非空「回文子序列」个数 。
通过从 s 中删除 0 个或多个字符来获得子序列。
如果一个字符序列与它反转后的字符序列一致，那么它是「回文字符序列」。
如果有某个 i , 满足 ai != bi ，则两个序列 a1, a2, … 和 b1, b2, … 不同。
注意：

  • 结果可能很大，你需要对 109 + 7 取模 。

示例 1：
输入：s = ‘bccb’ 输出：6 解释：6 个不同的非空回文子字符序列分别为：’b’, ‘c’, ‘bb’, ‘cc’, ‘bcb’, ‘bccb’。 注意：’bcb’ 虽然出现两次但仅计数一次。
示例 2：
输入：s = ‘abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba’ 输出：104860361 解释：共有 3104860382 个不同的非空回文子序列，104860361 对 109 + 7 取模后的值。

提示：

  • 1 <= s.length <= 1000
  • s[i] 仅包含 ‘a’, ‘b’, ‘c’ 或 ‘d’

思路：
如果只是求解所有回文子序列的个数，那很简单。难点在于如何去重，考虑到不同字符数只有四种，故可按左右端点处的字符区分不同回文串
区间DP + 单调队列优化或者是采用pre和ne数组记录每个位置之前和之后不同字符的首次出现位置
分三种情况

  • 长度为1的
  • 长度为2的

  • 长度大于2的，两端确定，就不会有重复

    1. class Solution {
    2. public int countPalindromicSubsequences(String s) {
    3.    int n = s.length(), mod = (int)(1e9+7);
    4.    int[][] f = new int[n][n];
    6.    for (int len = 1; len <= n; len++) {
    7.        Deque<Integer>[] q = new LinkedList[4];
    8.        for (int i = 0; i < 4; i++)
    9.            q[i] = new LinkedList<>();
    11.        for (int r = 0; r < n; r++) {
    12.            q[s.charAt(r) - 'a'].offer(r);
    13.            int l = r - len + 1;
    14.            if (l < 0) continue;
    15.            if (len == 1)
    16.                f[l][r] = 1;
    17.            else {
    18.                for (int i = 0; i < 4; i++) {
    19.                    while (!q[i].isEmpty() && q[i].peek() < l)
    20.                        q[i].poll();
    22.                    if (!q[i].isEmpty()) {
    23.                        f[l][r]++;
    24.                        int ll = q[i].peek(), rr = q[i].peekLast();
    25.                        if (ll + 1 <= rr)
    26.                            f[l][r]++;
    27.                        if (ll + 1 <= rr - 1)
    28.                            f[l][r] = (f[l][r] + f[ll + 1][rr - 1]) % mod;
    29.                    }
    30.                }
    31.            }
    32.        }
    33.    }
    34.    return f[0][n - 1];
    35. }
    36. }
  1. class Solution {
  2.     final int MOD = (int)(1e9 + 7);
  3.     public int countPalindromicSubsequences(String s) {
  4.         char[] ch = s.toCharArray();
  5.         int n = ch.length;
  6.         int[][] f = new int[n][n];
  8.         int[][] pre = new int[4][n], ne = new int[4][n];
  9.         for (int i = 0; i < 4; i++) {
  10.             Arrays.fill(pre[i], -1);
  11.             Arrays.fill(ne[i], n);
  12.         }
  14.         pre[ch[0] - 'a'][0] = 0;
  15.         for (int i = 1; i < n; i++) {
  16.             for (int j = 0; j < 4; j++)
  17.                 pre[j][i] = pre[j][i - 1];
  18.             pre[ch[i] - 'a'][i] = i;
  19.         }
  21.         ne[ch[n - 1] - 'a'][n - 1] = n - 1;
  22.         for (int i = n - 2; i >= 0; i--) {
  23.             for (int j = 0; j < 4; j++)
  24.                 ne[j][i] = ne[j][i + 1];
  25.             ne[ch[i] - 'a'][i] = i;
  26.         }
  29.         for (int len = 1; len <= n; len++) {
  30.             for (int l = 0; l + len - 1 < n; l++) {
  31.                 int r = l + len - 1;
  32.                 for (int i = 0; i < 4; i++) {
  33.                     int ll = ne[i][l], rr = pre[i][r];
  34.                     if (ll > rr) continue;
  35.                     f[l][r]++;
  36.                     if (ll + 1 <= rr)
  37.                         f[l][r]++;
  38.                     if (ll + 1 <= rr - 1)
  39.                         f[l][r] = (f[l][r] + f[ll + 1][rr - 1]) % MOD;
  40.                 }
  41.             }
  42.         }
  43.         return f[0][n - 1];
  44.     }
  45. }