Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. 
Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. 
In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

2⃣ Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния.
Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат.
Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат.

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

class Solution {

    function stoneGameII($piles) {
        $n = count($piles);
        $dp = array_fill(0, 2, array_fill(0, $n + 1, array_fill(0, $n + 1, -1)));

        function f($p, $i, $m, &$dp, &$piles) {
            if ($i == count($piles)) return 0;
            if ($dp[$p][$i][$m] != -1) return $dp[$p][$i][$m];
            $res = $p == 1 ? 1000000 : -1;
            $s = 0;
            for ($x = 1; $x <= min(2 * $m, count($piles) - $i); $x++) {
                $s += $piles[$i + $x - 1];
                if ($p == 0) {
                    $res = max($res, $s + f(1, $i + $x, max($m, $x), $dp, $piles));
                } else {
                    $res = min($res, f(0, $i + $x, max($m, $x), $dp, $piles));
                }
            }
            return $dp[$p][$i][$m] = $res;
        }

        return f(0, 0, 1, $dp, $piles);
    }
}

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

Задача: 1329. Sort the Matrix Diagonally
Сложность: medium

Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].

Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.

Пример:

Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]

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

1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.

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

3⃣Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.

😎 Решение:

class Solution {
    function diagonalSort($mat) {
        $m = count($mat);
        $n = count($mat[0]);
        $diagonals = [];

        for ($row = 0; $row < $m; $row++) {
            for ($col = 0; $col < $n; $col++) {
                $key = $row - $col;
                if (!isset($diagonals[$key])) {
                    $diagonals[$key] = [];
                }
                $diagonals[$key][] = $mat[$row][$col];
            }
        }

        foreach ($diagonals as &$diagonal) {
            sort($diagonal);
        }

        for ($row = 0; $row < $m; $row++) {
            for ($col = 0; $col < $n; $col++) {
                $key = $row - $col;
                $mat[$row][$col] = array_shift($diagonals[$key]);
            }
        }

        return $mat;
    }
}

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