algorithm - 矩阵中要删除的最小列以使其按行字典顺序排序

Question

我正在尝试解决这个招聘竞赛问题(现已结束)

Lexicographic Rows

You are given a matrix of characters. In one operation you can remove a column of the matrix. You can perform as many operations as you want. Your task is to make the final matrix interesting i.e. the string formed by the characters of row is lexicographically smaller or equal to the string formed by the characters of the row. You need to use minimum number of operations possible. An empty matrix is always a interesting matrix.

Input

The first line contains two integers and . The next lines contain letters each.

Output

In the output, you need to print the minimum number of operations to make the matrix interesting.

Constraints

There are only lowercase English alphabets as characters in the input.

Sample Input

3 3

cfg

agk

dlm

Sample Output

1

Explanation

Delete the first column to make the matrix interesting.

我非常确信这是一个 DP 问题。不过，我很难找到最佳子问题。我设法只通过了几个测试用例

我将 dp[i][j] 定义为要删除的最小列数，以获得有趣的矩阵。

对于每个字符 input[i][j] 都有两种可能性。

1. 如果前一个条目在字典顺序上是有效的，我们可以采用 dp[i][j - 1] 并且当前输入不会改变任何东西。
2. 否则我们检查 input[i -1][j] 和 input[i][j] 是否按照我们考虑的正确顺序 dp[i][j - 1] 否则这一列也是无效的，所以我们将 1 添加到 dp[i][j-1]<

我的解决方案。代码

int n, m;
cin >> n >> m;
vector<string> input(n);
for (int i = 0; i < n; ++i) {
    string temp = "";
    for (int j = 0; j < m; ++j) {
        char c;
        cin >> c;
        temp = temp + c;
    }
    input[i] = temp;
}

vector<vector<int> > dp(n, vector<int>(m, 0));

for (int i = 1; i < n; ++i) {
    for (int j = 1; j < m; ++j) {
        //Left is valid
        if (input[i - 1][j - 1] < input[i][j - 1]) {
            dp[i][j] = dp[i][j - 1];
        }
        else {
            //Current is valid
            if (input[i - 1][j] <= input[i][j]) {
                dp[i][j] = dp[i][j - 1];
            }
            else {
                dp[i][j] = dp[i][j - 1] + 1;
            }
        }
    }
}
cout << dp[n - 1][m - 1] << endl;

Answer 1

我们可以从左到右遍历列，选择那些不会使当前矩阵变得无趣的列。如果实现得当，这将花费与输入大小成线性关系的时间。

支持该算法的关键事实是，给定两个有趣的列子集，我们可以将其中一个缺失的第一列添加到另一个，而不会使它变得无趣。