Xóa cột để mảng chuỗi tăng dần III trong C++

Cho mảng A gồm N chuỗi cùng độ dài. Xóa một tập cột D sao cho sau khi xóa, mỗi chuỗi đều theo thứ tự từ điển (tăng dần). Tìm kích thước nhỏ nhất của D.

Ví dụ: ["cbcdb","ccbxc"] → 3.

Giải thuật

1. Tìm dãy con cột dài nhất (LIS) sao cho với mọi cặp cột j < i trong dãy, tất cả các hàng đều có A[k][j] ≤ A[k][i].
2. Dùng DP: lis[i] = độ dài dãy kết thúc tại cột i. ret = max(lis[i]).
3. Kết quả = m - ret (m là số cột). Nếu ret=0 trả về m-1.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int minDeletionSize(vector<string>& A){
        int ret = 0;
        int n = A.size();
        int m = A[0].size();
        vector<int> lis(m + 1, 1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < i; j++) {
                bool ok = true;
                for (int k = 0; k < n; k++) {
                    if (A[k][j] > A[k][i]) { ok = false; break; }
                }
                if (ok) {
                    lis[i] = max(lis[j] + 1, lis[i]);
                    ret = max(ret, lis[i]);
                }
            }
        }
        if (ret == 0) return m - 1;
        return m - ret;
    }
};
int main(){
    Solution ob;
    vector<string> v = {"cbcdb","ccbxc"};
    cout << (ob.minDeletionSize(v));
}

Đầu vào

{"cbcdb","ccbxc"}

Đầu ra

3