ลบคอลัมน์เพื่อให้เรียงลำดับ III ใน C++

คำอธิบายปัญหา

ให้อาร์เรย์ A ของ N สตริง ความยาวเท่ากัน เลือกชุดดัชนีคอลัมน์ D เพื่อลบ ทำให้แต่ละแถวของอาร์เรย์ที่เหลือเรียงลำดับ lexicographically (A[i][0] ≤ A[i][1] ≤ ...) หาขนาด D น้อยที่สุด

ตัวอย่าง

A = ["cbcdb","ccbxc"] → Output: 3

แนวทางแก้ปัญหา: Longest Increasing Subsequence (LIS) บนคอลัมน์

คอลัมน์ที่เก็บไว้ต้องเป็นลำดับที่ "สอดคล้อง" กับทุกแถวพร้อมกัน คือ ∀k, A[k][j₁] ≤ A[k][j₂] ≤ ... สำหรับคอลัมน์ที่เก็บไว้ j₁ < j₂ < ...

หา LIS ของคอลัมน์ โดยเปรียบเทียบคอลัมน์ i กับ j: ok = true ถ้า ∀k, A[k][i] ≤ A[k][j]

อัลกอริทึม

1. lis[i] = ความยาว LIS ที่จบที่คอลัมน์ i
2. สำหรับแต่ละ i, ลอง j < i ถ้า ok(j,i) → lis[i] = max(lis[i], lis[j]+1)
3. ret = max(lis[i])
4. คำตอบ = m - ret (m = จำนวนคอลัมน์)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minDeletionSize(vector<string>& A) {
        int n = A.size(), m = A[0].size();
        vector<int> lis(m+1, 1);
        int ret = 0;
        
        for(int i=0; i A[k][i]) { ok=false; break; }
                }
                if(ok) {
                    lis[i] = max(lis[i], lis[j]+1);
                    ret = max(ret, lis[i]);
                }
            }
        }
        return ret == 0 ? m-1 : m - ret;
    }
};

ความซับซ้อน

• เวลา: O(m² × n)
• พื้นที่: O(m)