Задача: 960. Delete Columns to Make Sorted III

Сложность: hard
Вам дан массив из n строк strs, все одинаковой длины.
Мы можем выбрать любые индексы для удаления, и мы удаляем все символы в этих индексах для каждой строки.

Например, если у нас есть strs = ["abcdef","uvwxyz"] и индексы удаления {0, 2, 3}, то итоговый массив после удаления будет ["bef", "vyz"].
Предположим, мы выбрали набор индексов удаления answer таким образом, что после удаления итоговый массив имеет каждую строку (ряд) в лексикографическом порядке. (т.е. (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]) и (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]) и так далее). Верните минимально возможное значение answer.length.

Пример:

Input: strs = ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]).
Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.

👨‍💻 Алгоритм:

1⃣Вместо поиска количества удаляемых столбцов, найдем количество столбцов, которые нужно сохранить. В конце мы можем вычесть это значение, чтобы получить желаемый ответ.

2⃣Используйте динамическое программирование, чтобы решить проблему. Пусть dp[k] будет количеством столбцов, которые сохраняются, начиная с позиции k. Мы будем искать максимальное значение dp[k], чтобы найти количество столбцов, которые нужно сохранить.

3⃣Итоговое количество удаляемых столбцов будет равно общей длине строк минус количество сохраненных столбцов.

😎 Решение:

class Solution {
    /**
     * @param String[] $A
     * @return Integer
     */
    function minDeletionSize($A) {
        $W = strlen($A[0]);
        $dp = array_fill(0, $W, 1);

        for ($i = $W - 2; $i >= 0; --$i) {
            for ($j = $i + 1; $j < $W; ++$j) {
                $valid = true;
                foreach ($A as $row) {
                    if ($row[$i] > $row[$j]) {
                        $valid = false;
                        break;
                    }
                }
                if ($valid) {
                    $dp[$i] = max($dp[$i], 1 + $dp[$j]);
                }
            }
        }

        return $W - max($dp);
    }
}

Ставь 👍 и забирай 📚 Базу знаний