Задача: 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 на последнем шаге.

😎 Решение:

public class Solution {
    public int KnightDialer(int n) {
        int MOD = 1000000007;
        int[][] moves = new int[][] {
            new int[] {4, 6},
            new int[] {6, 8},
            new int[] {7, 9},
            new int[] {4, 8},
            new int[] {0, 3, 9},
            new int[0],
            new int[] {0, 1, 7},
            new int[] {2, 6},
            new int[] {1, 3},
            new int[] {2, 4}
        };
        
        int[] dp = new int[10];
        Array.Fill(dp, 1);
        
        for (int step = 1; step < n; step++) {
            int[] newDp = new int[10];
            for (int i = 0; i < 10; i++) {
                foreach (int move in moves[i]) {
                    newDp[move] = (newDp[move] + dp[i]) % MOD;
                }
            }
            dp = newDp;
        }
        
        int sum = 0;
        foreach (int count in dp) {
            sum = (sum + count) % MOD;
        }
        return sum;
    }
}

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