935. Knight Dialer
leetcode medium
Task
Шахматный конь обладает уникальным движением: он может перемещаться на две клетки по вертикали и одну клетку по горизонтали, или на две клетки по горизонтали и одну клетку по вертикали (при этом обе клетки образуют форму буквы L). Возможные движения шахматного коня показаны на этой диаграмме: Шахматный конь может двигаться так, как показано на шахматной диаграмме ниже: У нас есть шахматный конь и телефонная панель, как показано ниже, конь может стоять только на числовой клетке (то есть на синей клетке).
Учитывая целое число n, верните, сколько различных телефонных номеров длины n мы можем набрать. Вам разрешается сначала поставить коня на любую цифровую клетку, а затем выполнить n - 1 прыжков, чтобы набрать номер длины n. Все прыжки должны быть правильными прыжками коня. Поскольку ответ может быть очень большим, верните ответ по модулю 10^9 + 7.
Пример:
Input: n = 1
Output: 10
C# solution
matched/originalpublic 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;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
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}
};
vector<int>& dp = new int[10];
Array.Fill(dp, 1);
for (int step = 1; step < n; step++) {
vector<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;
}
}Java solution
auto-draft, review before submitimport java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
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;
}
}JavaScript solution
matched/originalvar knightDialer = function(n) {
const MOD = 10**9 + 7;
const 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]
};
let dp = new Array(10).fill(1);
for (let step = 1; step < n; step++) {
const newDp = new Array(10).fill(0);
for (let i = 0; i < 10; i++) {
for (const move of moves[i]) {
newDp[move] = (newDp[move] + dp[i]) % MOD;
}
}
dp = newDp;
}
return dp.reduce((acc, val) => (acc + val) % MOD, 0);
};Python solution
matched/originalMOD = 10**9 + 7
def knightDialer(n):
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 = [1] * 10
for _ in range(n - 1):
new_dp = [0] * 10
for i in range(10):
for move in moves[i]:
new_dp[move] = (new_dp[move] + dp[i]) % MOD
dp = new_dp
return sum(dp) % MODGo solution
matched/originalpackage main
const MOD = 1000000007
func knightDialer(n int) int {
moves := map[int][]int{
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 := make([]int, 10)
for i := range dp {
dp[i] = 1
}
for step := 1; step < n; step++ {
newDp := make([]int, 10)
for i := 0; i < 10; i++ {
for _, move := range moves[i] {
newDp[move] = (newDp[move] + dp[i]) % MOD
}
}
dp = newDp
}
sum := 0
for _, count := range dp {
sum = (sum + count) % MOD
}
return sum
}Explanation
Algorithm
Определить возможные движения коня с каждой цифровой клетки.
Использовать динамическое программирование для хранения количества способов достижения каждой цифровой клетки на каждом шаге.
Инициализировать массив DP количеством способов набора телефонного номера длины 1 для каждой цифровой клетки (это просто 1).
На каждом шаге обновлять массив DP, переходя по всем возможным движениям коня.
Вернуть сумму всех значений в массиве DP на последнем шаге.
😎