目标
给定由 n 个小写字母字符串组成的数组 strs ，其中每个字符串长度相等。
选取一个删除索引序列，对于 strs 中的每个字符串，删除对应每个索引处的字符。
比如，有 strs = ["abcdef","uvwxyz"] ，删除索引序列 {0, 2, 3} ，删除后为 ["bef", "vyz"] 。
假设，我们选择了一组删除索引 answer ，那么在执行删除操作之后，最终得到的数组的行中的 每个元素 都是按字典序排列的（即 (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) 和 (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) ，依此类推）。
请返回 answer.length 的最小可能值 。
示例 1：
输入：strs = ["babca","bbazb"]
输出：3
解释：
删除 0、1 和 4 这三列后，最终得到的数组是 strs = ["bc", "az"]。
这两行是分别按字典序排列的（即，strs[0][0] <= strs[0][1] 且 strs[1][0] <= strs[1][1]）。
注意，strs[0] > strs[1] —— 数组 strs 不一定是按字典序排列的。示例 2：
输入：strs = ["edcba"]
输出：4
解释：如果删除的列少于 4 列，则剩下的行都不会按字典序排列。示例 3：
输入：strs = ["ghi","def","abc"]
输出：0
解释：所有行都已按字典序排列。说明：
- n == strs.length
- 1 <= n <= 100
- 1 <= strs[i].length <= 100
- strs[i] 由小写英文字母组成
思路
有一个元素长度相同的字符串数组 strs，通过删除列使得每个元素内部的字母是非严格递增的，返回删除的最少列数。
定义 dp[i] 表示以 i 列结尾的最长子序列长度，注意每一行都应该是非严格递增的。对于所有 j < i，如果 j 列均小于等于 i 列，dp[i] = Math.max(dp[i], dp[j] + 1)。
代码
/**
* @date 2025-12-22 9:09
*/
public class MinDeletionSize960 {
public int minDeletionSize(String[] strs) {
int n = strs[0].length();
int[] dp = new int[n];
Arrays.fill(dp, 1);
int res = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (isIncrease(i, j, strs)) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
res = Math.max(res, dp[i]);
}
return n - res;
}
public boolean isIncrease(int i, int j, String[] strs) {
for (String str : strs) {
if (str.charAt(j) > str.charAt(i)) {
return false;
}
}
return true;
}
}
性能
