C++刷leetcode（960. 删列造序 III）【动态规划】
题目描述：给定由 N 个小写字母字符串组成的数组 A，其中每个字符串长度相等。
选取一个删除索引序列，对于 A 中的每个字符串，删除对应每个索引处的字符。
比如，有 A = ["babca","bbazb"]，删除索引序列 {0, 1, 4}，删除后 A 为["bc","az"]。
假设，我们选择了一组删除索引 D，那么在执行删除操作之后，最终得到的数组的行中的每个元素都是按字典序排列的。
清楚起见，A 是按字典序排列的（即，A <= A <= ... <= A.length - 1]），A 是按字典序排列的（即，A <= A <= ... <= A.length - 1]），依此类推。
请你返回 D.length 的最小可能值。
示例 1：
输入：["babca","bbazb"]
输出：3
解释：
删除 0、1 和 4 这三列后，最终得到的数组是 A = ["bc", "az"]。
这两行是分别按字典序排列的（即，A <= A 且 A <= A）。
注意，A > A —— 数组 A 不一定是按字典序排列的。
示例 2：
输入：["edcba"]
输出：4
解释：如果删除的列少于 4 列，则剩下的行都不会按字典序排列。
示例 3：
输入：["ghi","def","abc"]
输出：0
解释：所有行都已按字典序排列。
提示：
1 <= A.length <= 100
1 <= A.length <= 100
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/delete-columns-to-make-sorted-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
int len1 = strs.size(), len2 =strs.size();
vector<vector<int> >dp(len2, vector<int>(2,1));
//初始化
dp = 1;
dp = 0;
//动态规划
for(int i = 1; i < len2; i++){
//dp删除当前元素得到的最大长度
dp = max(dp, dp);
//dp保留当前元素得到的最大长度
for(int k = i-1; k >= 0 ; k--){
bool flag = true;
for(int j = 0; j < len1; j++){
if(strs > strs){
flag = false;
break;
}
}
if(flag == true){
dp = max(dp, dp + 1);
}
}
}
return len2 - max(dp, dp);
}
}; {:10_329:}
页:
[1]