leetcode 960

960: 删列造序Ⅲ

思路：求删除最少，考虑最多能保留多少列；动态规划dp，问题等价于计算数组 strs 中的所有字符串的最长公共递增子序列的长度，这里的公共的含义是下标相同。

class Solution { public: int minDeletionSize(vector<string>& strs) { int n = strs.size(),m = strs[0].size(); vector<int> dp(m, 1); // dp[j] 以第j列结尾的最长合法列子序列长度 int maxKeep = 1; // 最多能保留多少列 for (int j = 1; j < m; j++) { for (int i = 0; i < j; i++) { bool valid = true; for (int r = 0; r < n; r++) { if (strs[r][i] > strs[r][j]){ valid = false; break; } } if (valid) dp[j] = max(dp[j], dp[i] + 1); } maxKeep = max(maxKeep, dp[j]); } return m - maxKeep; // 总列数减去保留的列数 } };