Задача: 935. Knight Dialer
Сложность: medium

Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).


Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.

Пример:

Input: n = 1
Output: 10

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

1⃣Определить возможные движения коня с каждой цифровой клетки.
Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге.

2⃣Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.

3⃣Вернуть сумму всех значений в массиве DP на последнем шаге.

😎 Решение:

function knightDialer($n) {
    $MOD = 1000000007;
    $moves = [
        0 => [4, 6],
        1 => [6, 8],
        2 => [7, 9],
        3 => [4, 8],
        4 => [0, 3, 9],
        5 => [],
        6 => [0, 1, 7],
        7 => [2, 6],
        8 => [1, 3],
        9 => [2, 4]
    ];
    
    $dp = array_fill(0, 10, 1);
    
    for ($step = 1; $step < $n; $step++) {
        $newDp = array_fill(0, 10, 0);
        foreach ($dp as $i => $count) {
            foreach ($moves[$i] as $move) {
                $newDp[$move] = ($newDp[$move] + $count) % $MOD;
            }
        }
        $dp = $newDp;
    }
    
    return array_reduce($dp, function($acc, $val) use ($MOD) {
        return ($acc + $val) % $MOD;
    }, 0);
}

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