LeetCode 960. 删列造序 III

Categories:

题目描述
思路分析
1. 解法一：列序 DP（推荐）
相似题目

题目描述

✅ 960. 删列造序 III

思路分析

解法一：列序 DP（推荐）

核心思路：

把每一列视为一个“字符”，判断列之间是否满足所有行的非递减关系。

dp[j] 表示以第 j 列结尾的最长合法列序列长度。

若对所有行 strs[r][i] <= strs[r][j]，则可从 i 转移到 j。

答案为 m - max(dp)。

复杂度分析：

时间复杂度：O(m^2 * n)，其中 m 为列数，n 为字符串数量。

空间复杂度：O(m)。

import java.util.Arrays;

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();
        int[] dp = new int[m];
        Arrays.fill(dp, 1);
        int best = 1;

        for (int j = 0; j < m; j++) {
            for (int i = 0; i < j; i++) {
                boolean ok = true;
                for (int r = 0; r < n; r++) {
                    if (strs[r].charAt(i) > strs[r].charAt(j)) {
                        ok = false;
                        break;
                    }
                }
                if (ok) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }
            best = Math.max(best, dp[j]);
        }

        return m - best;
    }
}

func minDeletionSize(strs []string) int {
	n := len(strs)
	m := len(strs[0])
	dp := make([]int, m)
	for i := 0; i < m; i++ {
		dp[i] = 1
	}

	best := 1
	for j := 0; j < m; j++ {
		for i := 0; i < j; i++ {
			ok := true
			for r := 0; r < n; r++ {
				if strs[r][i] > strs[r][j] {
					ok = false
					break
				}
			}
			if ok && dp[i]+1 > dp[j] {
				dp[j] = dp[i] + 1
			}
		}
		if dp[j] > best {
			best = dp[j]
		}
	}

	return m - best
}

相似题目

题目	难度	考察点
300. 最长递增子序列	中等	DP
583. 两个字符串的删除操作	中等	DP
1143. 最长公共子序列	中等	DP
1335. 工作计划的最低难度	困难	DP
1048. 最长字符串链	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/81179271