Ход конем на телефонной клавиатуре

Источник: https://leetcode.com/problems/knight-dialer/

Шахматный конь ходит буквой Г: две клетки в любом направлении по вертикали/горизонтали, и ещё одна клетка в перпендикулярном направлении по горизонтали/вертикали. Все возможные ходы показаны на диаграмме:

Допустим, конь ходит по телефонной клавиатуре, только по кнопкам с цифрами (синие кнопки на диаграмме ниже):

Дано целое числоn, подсчитать, сколько различных номеров можно набрать за n ходов.

Ответ можно вернуть по модулю109 + 7.

Пример 1:

Дано: n = 1
Результат: 10
Пояснение: Нам нужно набрать номер длинной 1, поэтому нужно расположить коня в каждой из 10 кнопок - и это и будет результат.

Пример 2:

Дано: n = 2
Результат: 20
Пояснение: Мы можем набрать: [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, 49, 60, 61, 67, 72, 76, 81, 83, 92, 94]

Пример 3:

Дано: n = 3
Результат: 46

Пример 4:

Дано: n = 4
Результат: 104

Пример 5:

Дано: n = 3131
Результат: 136006598
Пояснение: Принимаем во внимание результат по модулю.

Ограничения:

• 1 <= n <= 5000


Имплементация

class Solution {
    public int knightDialer(int N) {
        long MOD = 1000000007;
        long[] counts = new long[10];
// номер длинной в 1 цифру можно получить за 1 ход
        Arrays.fill(counts, 1);
        long[] temp;

        for (int i=1; i<=N-1; i++) {
            temp = counts.clone();
// из кнопки 0 конь может перейти в 4 и 6
// из 1 - в 6 и 8
// из 2 - в 7 и 9
// из 3 - в 4 и 8
// из 4 - в 3, 9 и 0
// из 5 - никуда
// из 6 - в 1, 7 и 0
// из 7 - в 2 и 6
// из 8 - в 1 и 3
// из 9 - в 2 и 4

// Значит, количество способов, которыми можно перейти в кнопку 0 - это
// сумма способов, которыми можно перейти в 4 и 6. И так далее.

// зафиксируем это ниже с учетом модуля:
            counts[0] = (temp[4] + temp[6]) % MOD;
            counts[1] = (temp[6] + temp[8]) % MOD;
            counts[2] = (temp[7] + temp[9]) % MOD;
            counts[3] = (temp[4] + temp[8]) % MOD;
            counts[4] = (temp[3] + temp[9] + temp[0]) % MOD;
            counts[5] = 0;
            counts[6] = (temp[1] + temp[7] + temp[0]) % MOD;
            counts[7] = (temp[2] + temp[6]) % MOD;
            counts[8] = (temp[1] + temp[3]) % MOD;
            counts[9] = (temp[2] + temp[4]) % MOD;
        }
       
// мы сделали симуляцию n шагов
// теперь в массиве counts у нас хранится, сколькими способами мы попали
// в каждую кнопку через n шагов.
// Чтобы получить финальный результат, нужно просуммировать все элементы
// по модулю
        long sum = 0;
        for (int i = 0; i < counts.length; i++) {
            sum = (sum + counts[i]%MOD) % MOD;
        }
// и возвращаем результат по модулю
        return (int) (sum % MOD);

    }
}