960.删列造序 III：动态规划(最长递增子序列)

【LetMeFly】960.删列造序 III：动态规划(最长递增子序列)

力扣题目链接：https://leetcode.cn/problems/delete-columns-to-make-sorted-iii/

给定由 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] 由小写英文字母组成

解题方法：动态规划

这道题可以换个角度思考：求最少删除列使剩余元素非递减 相当于 求最长非递减子序列。子序列外的其他列就是要删除的列。

好了，这就和300.最长递增子序列大同小异了。

使用一个dp数组，其中dp[i]表示strs每一行都以第i个元素结尾时，最多保留的非递减列数。那么总列数 - max(dp[i])即为所求。

两层循环，第一层循环从0到len(strs[0])枚举并计算dp[cur]，怎么计算呢？

第二层循环从0到cur-1枚举prev，如果strs中每一行的cur列都大于等于prev列，并且以prev列结尾的非递减序列还比当前以cur结尾的非递减序列长，那么是不是就说明prev这一列可以拼接到cur这一列的后面了（更新dp[cur] = dp[prev] + 1）。

• 时间复杂度$O(nm^2)$，其中$m=len(strs[0])$
• 空间复杂度$O(m)$

AC代码

C++

/*
 * @LastEditTime: 2025-12-22 22:43:18
 */
class Solution {
private:
    bool can(vector<string>& strs, int i, int j) {
        for (string& s : strs) {
            if (s[i] < s[j]) {
                return false;
            }
        }
        return true;
    }
public:
    int minDeletionSize(vector<string>& strs) {
        int m = strs[0].size();
        vector<int> dp(m);
        for (int i = 0; i < m; i++) {  // 一定要从0开始！！要不然dp[0]恒为0
            for (int j = 0; j < i; j++) {
                if (dp[j] > dp[i] && can(strs, i, j)) {
                    dp[i] = dp[j];
                }
            }
            dp[i]++;
        }
        return m - *max_element(dp.begin(), dp.end());
    }
};

Python

'''
LastEditTime: 2025-12-22 22:49:18
'''
from typing import List

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        m = len(strs[0])
        dp = [0] * m
        for cur in range(m):
            for prev in range(cur):
                if dp[cur] < dp[prev] and all(s[prev] <= s[cur] for s in strs):
                    dp[cur] = dp[prev]
            dp[cur] += 1
        return m - max(dp)

Java

/*
 * @LastEditTime: 2025-12-22 22:59:50
 */
class Solution {
    private boolean can(String[] strs, int prev, int cur) {
        for (String s : strs) {
            if (s.charAt(prev) > s.charAt(cur)) {
                return false;
            }
        }
        return true;
    }

    public int minDeletionSize(String[] strs) {
        int m = strs[0].length();
        int[] dp = new int[m];
        int longest = 0;
        for (int cur = 0; cur < m; cur++) {
            for (int prev = 0; prev < cur; prev++) {
                if (dp[cur] < dp[prev] && can(strs, prev, cur)) {
                    dp[cur] = dp[prev];
                }
            }
            longest = Math.max(longest, ++dp[cur]);
        }
        return m - longest;
    }
}

Go

/*
 * @LastEditTime: 2025-12-22 22:53:21
 */
package main

import "slices"

func can960(strs []string, prev, cur int) bool {
    for _, s := range strs {
        if s[prev] > s[cur] {
            return false
        }
    }
    return true
}

func minDeletionSize(strs []string) int {
    m := len(strs[0])
    dp := make([]int, m)
    for cur := 0; cur < m; cur++ {
        for prev := 0; prev < cur; prev++ {
            if dp[cur] < dp[prev] && can960(strs, prev, cur) {
                dp[cur] = dp[prev]
            }
        }
        dp[cur]++
    }
    return m - slices.Max(dp)
}

• 执行用时分布0ms击败100.00%
• 消耗内存分布5.24MB击败100.00%

Rust

/*
 * @LastEditTime: 2025-12-22 23:05:28
 */
impl Solution {
    pub fn min_deletion_size(strs: Vec<String>) -> i32 {
        let m = strs[0].len();
        let mut dp = vec![0; m];
        for cur in 0..m {
            for prev in 0..cur {
                if dp[prev] > dp[cur] && strs.iter().all(|s| s.as_bytes()[prev] <= s.as_bytes()[cur]) {
                    dp[cur] = dp[prev];
                }
            }
            dp[cur] += 1;
        }
        m as i32 - *dp.iter().max().unwrap()
    }
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源